Coluna.ColunaBase.BoundMethod
Bound(min, primal)

Create a default primal bound for a problem with objective sense (min or max) in the space (primal or dual).

Coluna.ColunaBase.SolutionMethod

Solution is an internal data structure of Coluna and should not be used in algorithms. See MathProg.PrimalSolution & MathProg.DualSolution instead.

Solution(
model::AbstractModel,
decisions::Vector,
values::Vector,
solution_value::Float64,
status::SolutionStatus
)

Create a solution to the model. Other arguments are:

• decisions is a vector with the index of each decision.
• values is a vector with the values for each decision.
• solution_value is the value of the solution.
• status is the solution status.
Coluna.ColunaBase.SolutionStatusType
SolutionStatus

Description of the solution statuses:

• FEASIBLE_SOL : the solution is feasible
• INFEASIBLE_SOL : the solution is not feasible

If there is no solution or if we don't have information about the solution, the solution status should be :

• UNKNOWN_SOLUTION_STATUS
Coluna.ColunaBase.TerminationStatusType
TerminationStatus

Theses statuses are the possible reasons why an algorithm stopped the optimization. When a subsolver is called through MOI, the MOI TerminationStatusCode is translated into a Coluna TerminationStatus.

Description of the termination statuses:

• OPTIMAL : the algorithm found a global optimal solution given the optimality tolerance
• INFEASIBLE : the algorithm proved infeasibility
• UNBOUNDED : the algorithm proved unboundedness
• TIME_LIMIT : the algorithm stopped because of the time limit
• NODE_LIMIT : the branch-and-bound based algorithm stopped due to the node limit
• OTHER_LIMIT : the algorithm stopped because of a limit that is neither the time limit

nor the node limit

If the algorithm has not been called, the default value of the termination status should be:

• OPTIMIZE_NOT_CALLED

If the conversion of a MOI.TerminationStatusCode returns UNCOVERED_TERMINATION_STATUS, Coluna should stop because it enters in an undefined behavior.

Coluna.ColunaBase.convert_statusMethod
convert_status(status::MOI.TerminationStatusCode) -> Coluna.TerminationStatus
convert_status(status::Coluna.TerminationStatus) -> MOI.TerminationStatusCode
convert_status(status::MOI.ResultStatusCode) -> Coluna.SolutionStatus
convert_status(status::Coluna.SolutionStatus) -> MOI.ResultStatusCode

Convert a termination or solution status of a given type to the corresponding status in another type. This method is used to communicate between Coluna and MathOptInterface.

Coluna.ColunaBase.create_recordMethod
create_record(storage, storage_unit_type)

Returns a Record that contains a description of the state of the storage unit at the time when the method is called.

Coluna.ColunaBase.diffMethod
diff(pb, db)
diff(db, pb)

Distance between a primal bound and a dual bound that have the same objective sense. Distance is non-positive if dual bound reached primal bound.

Coluna.ColunaBase.isbetterMethod
isbetter(b1, b2)

Returns true if bound b1 is better than bound b2. The function take into account the space (primal or dual) and the objective sense (min, max) of the bounds.

Coluna.ColunaBase.printboundsFunction
printbounds(db, pb [, io])

Prints the lower and upper bound according to the objective sense.

Can receive io::IO as an input, to eventually output the print to a file or buffer.

Coluna.ColunaBase.@nestedenumMacro
@nestedenum block_expression

Create a NestedEnum subtype such as :

Example

DocTestSetup = quote
using Coluna
end
Coluna.ColunaBase.@nestedenum begin
TypeOfItem
ItemA <= TypeOfItem
ChildA1 <= ItemA
GrandChildA11 <= ChildA1
GrandChildA12 <= ChildA1
ChildA2 <= ItemA
ItemB <= TypeOfItem
ItemC <= TypeOfItem
end

# output


Create a nested enumeration with items ItemA, ChildA1, ChildA2, GrandChildA11, GrandChildA12, ItemB, and ItemC of type TypeOfItem. The operator <= indicates the parent of the item.

julia> GrandChildA11 <= ItemA
true
julia> GrandChildA11 <= ItemC
false
DocTestSetup = nothing
Coluna.Benders.benders_output_typeMethod
benders_output_type(context) -> Type{<:AbstractBendersOutput}

Returns the type of the custom object that will store the output of the Benders cut generation algorithm.

Coluna.Benders.optimize_master_problem!Method
optimize_master_problem!(master, context, env) -> MasterResult

Returns an instance of a custom object MasterResult that implements the following methods:

• is_unbounded(res::MasterResult) -> Bool
• is_infeasible(res::MasterResult) -> Bool
• is_certificate(res::MasterResult) -> Bool
• get_primal_sol(res::MasterResult) -> Union{Nothing, PrimalSolution}
Coluna.Benders.optimize_separation_problem!Method
optimize_separation_problem!(context, sp_to_solve, env, unbounded_master) -> SeparationResult

Returns an instance of a custom object SeparationResult that implements the following methods:

• is_unbounded(res::SeparationResult) -> Bool
• is_infeasible(res::SeparationResult) -> Bool
• get_obj_val(res::SeparationResult) -> Float64
• get_primal_sol(res::SeparationResult) -> Union{Nothing, PrimalSolution}
• get_dual_sp_sol(res::SeparationResult) -> Union{Nothing, DualSolution}
Coluna.Benders.push_in_set!Method
push_in_set!(context, cut_pool, sep_result) -> Bool

Inserts a cut in the set of cuts generated at a given iteration of the Benders cut generation algorithm. The cut_pool structure is generated by set_of_cuts(context).

push_in_set!(context, sep_sp_sols, sep_result) -> Bool

Inserts a primal solution to a separation problem in the set of primal solutions generated at a given iteration of the Benders cut generation algorithm. The sep_sp_sols structure is generated by set_of_sep_sols(context).

Returns true if the cut or the primal solution was inserted in the set, false otherwise.

Coluna.Benders.set_of_cutsMethod

Returns an empty container that will store all the cuts generated by the separation problems during an iteration of the Benders cut generation algorithm. One must be able to iterate on this container to insert the cuts in the master problem.

Coluna.Benders.treat_infeasible_separation_problem_case!Method
treat_infeasible_separation_problem_case!(context, sp_to_solve, env, unbounded_master) -> SeparationResult

When after a call to optimize_separation_problem!, the separation problem is infeasible, this method is called. Returns an instance of a custom object SeparationResult.

Coluna.Benders.treat_unbounded_master_problem_case!Method
treat_unbounded_master_problem_case!(master, context, env) -> MasterResult

When after a call to optimize_master_problem!, the master is unbounded, this method is called. Returns an instance of a custom object MasterResult.

Coluna.Benders.update_sp_rhs!Method
update_sp_rhs!(context, sp, mast_primal_sol)

Updates the right-hand side of the separation problem sp by fixing the first-level solution obtained by solving the master problem mast_primal_sol.

Coluna.Algorithm.AbstractConquerAlgorithmType
AbstractConquerAlgorithm

This algorithm type is used by the tree search algorithm to update the incumbents and the formulation. For the moment, a conquer algorithm can be run only on reformulation. A conquer algorithm should restore records of storage units using restore_from_records!(conquer_input)

• each time it runs in the beginning
• each time after calling a child manager algorithm
Coluna.Algorithm.AbstractConquerInputType

AbstractConquerInput

Input of a conquer algorithm used by the tree search algorithm. Contains the node in the search tree and the collection of units to restore before running the conquer algorithm. This collection of units is passed in the input so that it is not obtained each time the conquer algorithm runs.

Coluna.Algorithm.AbstractOptimizationAlgorithmType
AbstractOptimizationAlgorithm

This type of algorithm is used to "bound" a model, i.e. to improve primal
and dual bounds of the model. Solving to optimality is a special case of "bounding".
The input of such algorithm should be of type OptimizationState.
The output of such algorithm should be of type OptimizationState.
Coluna.Algorithm.BendersCutGenerationType
Coluna.Algorithm.BendersCutGeneration(
restr_master_solve_alg = SolveLpForm(get_dual_sol = true, relax_integrality = true),
restr_master_optimizer_id = 1,
separation_solve_alg = SolveLpForm(get_dual_sol = true, relax_integrality = true)
max_nb_iterations::Int = 100,
)

Benders cut generation algorithm that can be applied to a formulation reformulated using Benders decomposition.

This algorithm is an implementation of the generic algorithm provided by the Benders submodule.

Parameters:

• restr_master_solve_alg: algorithm to solve the restricted master problem
• restr_master_optimizer_id: optimizer id to use to solve the restricted master problem
• separation_solve_alg: algorithm to solve the separation problem (must be a LP solver that returns a dual solution)

Option:

• max_nb_iterations: maximum number of iterations

At each iteration, the Benders cut generation algorithm show following statistics:

<it=  6> <et= 0.05> <mst= 0.00> <sp= 0.00> <cuts= 0> <master=  293.5000>

where:

• it stands for the current number of iterations of the algorithm
• et is the elapsed time in seconds since Coluna has started the optimisation
• mst is the time in seconds spent solving the master problem at the current iteration
• sp is the time in seconds spent solving the separation problem at the current iteration
• cuts is the number of cuts generated at the current iteration
• master is the objective value of the master problem at the current iteration

Debug options (print at each iteration):

• debug_print_master: print the master problem
• debug_print_master_primal_solution: print the master problem with the primal solution
• debug_print_master_dual_solution: print the master problem with the dual solution (make sure the restr_master_solve_alg returns a dual solution)
• debug_print_subproblem: print the subproblem
• debug_print_subproblem_primal_solution: print the subproblem with the primal solution
• debug_print_subproblem_dual_solution: print the subproblem with the dual solution
• debug_print_generated_cuts: print the generated cuts
Coluna.Algorithm.BendersIterationOutputType

Output of the default implementation of an iteration of the Benders algorithm.

It contains:

• min_sense: the original problem is a minimization problem
• nb_new_cuts: the number of new cuts added to the master problem
• ip_primal_sol: the primal solution to the original problem found during this iteration
• infeasible: the original problem is infeasible
• time_limit_reached: the time limit was reached
• master: the solution value to the master problem
Coluna.Algorithm.BendersMasterResultType

Output of the default implementation of the Benders.optimize_master_problem! method.

It contains:

• ip_solver: true if the master problem is solved with a MIP solver and involves integral variables, false otherwise.
• result: the result of the master problem optimization stored in an OptimizationState object.
• infeasible: true if the master at the current iteration is infeasible; false otherwise.
• unbounded: true if the master at the current iteration is unbounded; false otherwise.
• certificate: true if the master at the current iteration is unbounded and if the current result is a dual infeasibility certificate, false otherwise.
Coluna.Algorithm.BendersOutputType

Output of the default implementation of the Benders algorithm.

It contains:

• infeasible: the original problem is infeasible
• time_limit_reached: the time limit was reached
• mlp: the final bound obtained with the Benders cut algorithm
• ip_primal_sol: the best primal solution to the original problem found by the Benders cut algorithm
Coluna.Algorithm.BendersPrinterContextType
BendersPrinterContext(reformulation, algo_params) -> BendersPrinterContext

Creates a context to run the default implementation of the Benders algorithm together with a printer that prints information about the algorithm execution.

Coluna.Algorithm.BendersSeparationResultType

Output of the default implementation of the Benders.optimize_separation_problem! and Benders.treat_infeasible_separation_problem_case! methods.

It contains:

• second_stage_estimation_in_master: the value of the second stage cost variable in the solution to the master problem.
• second_stage_cost: the value of the second stage cost variable in the solution to the separation problem.
• lp_primal_sol: the primal solution to the separation problem.
• infeasible: true if the current separation problem is infeasible; false otherwise.
• unbounded: true if the current separation problem is unbounded; false otherwise.
• cut: the cut generated by the separation problem.
• infeasible_treatment: true if this object is an output of the Benders.treat_infeasible_separation_problem_case! method; false otherwise.
• unbounded_master: true if the separation subproblem has the form of Lemma 2 to separate a cut to truncate an unbounded ray of the restricted master problem; false otherwise.
Coluna.Algorithm.BranchingPhaseType
BranchingPhase(max_nb_candidates, conquer_algo, score)

Define a phase in strong branching. It contains the maximum number of candidates to evaluate, the conquer algorithm which does evaluation, and the score used to sort the candidates.

Coluna.Algorithm.ClassicBranchingType
ClassicBranching(
selection_criterion = MostFractionalCriterion()
rules = [Branching.PrioritisedBranchingRule(SingleVarBranchingRule(), 1.0, 1.0)]
int_tol = 1e-6
)

Chooses the best candidate according to a selection criterion and generates the two children.

Parameters

• selection_criterion: selection criterion to choose the best candidate
• rules: branching rules to generate the candidates
• int_tol: tolerance to determine if a variable is integer

It is implemented as a specific case of the strong branching algorithm.

Coluna.Algorithm.ColCutGenConquerType
Coluna.Algorithm.ColCutGenConquer(
colgen = ColumnGeneration(),
cutgen = CutCallbacks(),
primal_heuristics = ParameterizedHeuristic[ParamRestrictedMasterHeuristic()],
max_nb_cut_rounds = 3
)

Column-and-cut-generation based algorithm to find primal and dual bounds for a problem decomposed using Dantzig-Wolfe paradigm.

Parameters :

• colgen: column generation algorithm
• cutgen: cut generation algorithm
• primal_heuristics: heuristics to find a feasible solution
• max_nb_cut_rounds : number of cut generation done by the algorithm
Coluna.Algorithm.ColGenContextType
ColGenContext(reformulation, algo_params) -> ColGenContext

Creates a context to run the default implementation of the column generation algorithm.

Coluna.Algorithm.ColGenMasterResultType

Output of the ColGen.optimize_master_lp_problem! method.

Contains result, an OptimizationState object that is the output of the SolveLpForm algorithm called to optimize the master LP problem.

Coluna.Algorithm.ColGenPhase0Type

Phase 0 is a mix of phase 1 and phase 2. It sets a very large cost to artifical variables to force them to be removed from the master LP solution. If the final master LP solution contains artifical variables either the master is infeasible or the cost of artificial variables is not large enough. Phase 1 must be run.

Coluna.Algorithm.ColGenPhase2Type

Phase 2 solves the master LP without artificial variables. To start, it requires a set of columns that forms a feasible solution to the LP master. This set is found with phase 1.

Coluna.Algorithm.ColGenPricingResultType

Output of the default implementation of ColGen.optimize_pricing_problem!.

It contains:

• result: the output of the SolveIpForm algorithm called to optimize the pricing subproblem
• columns: a vector of GeneratedColumn objects obtained by processing of the output of pricing subproblem optimization, it stores the reduced cost of each column
• best_red_cost: the best reduced cost of the columns
Coluna.Algorithm.ColGenPrinterContextType
ColGenPrinterContext(reformulation, algo_params) -> ColGenPrinterContext

Creates a context to run the default implementation of the column generation algorithm together with a printer that prints information about the algorithm execution.

Coluna.Algorithm.ColGenStabType

Implementation of the "Smoothing with a self adjusting parameter" described in the paper of Pessoa et al.

TODO: docstring

• in: stability center
• dual solution of the previous iteration under Neame rule,
• incumbent dual solution under Wentges rule.
• out: current dual solution
• sep: smoothed dual solution π^sep <- α * π^in + (1 - α) * π^out
Coluna.Algorithm.ColGenStageIteratorType

Default implementation of the column generation stages works as follows.

Consider a set {A,B,C} of subproblems each of them associated to the following sets of pricing solvers: {a1, a2, a3}, {b1, b2}, {c1, c2, c3, c4}. Pricing solvers a1, b1, c1 are exact solvers; others are heuristic.

The column generation algorithm will run the following stages:

• stage 4 with pricing solvers {a3, b2, c4}
• stage 3 with pricing solvers {a2, b1, c3}
• stage 2 with pricing solvers {a1, b1, c2}
• stage 1 with pricing solvers {a1, b1, c1} (exact stage)

Column generation moves from one stage to another when all solvers find no column.

Coluna.Algorithm.ColumnGenerationType
Coluna.Algorithm.ColumnGeneration(
restr_master_solve_alg = SolveLpForm(get_dual_sol = true),
pricing_prob_solve_alg = SolveIpForm(
moi_params = MoiOptimize(
deactivate_artificial_vars = false,
enforce_integrality = false
)
),
essential_cut_gen_alg = CutCallbacks(call_robust_facultative = false),
strict_integrality_check = false,
max_nb_iterations = 1000,
log_print_frequency = 1,
redcost_tol = 1e-4,
cleanup_threshold = 10000,
cleanup_ratio = 0.66,
smoothing_stabilization = 0.0 # should be in [0, 1],
)

Column generation algorithm that can be applied to formulation reformulated using Dantzig-Wolfe decomposition.

This algorithm first solves the linear relaxation of the master (master LP) using restr_master_solve_alg. Then, it solves the subproblems by calling pricing_prob_solve_alg to get the columns that have the best reduced costs and that hence, may improve the master LP's objective the most.

In order for the algorithm to converge towards the optimal solution of the master LP, it suffices that the pricing oracle returns, at each iteration, a negative reduced cost solution if one exists. The algorithm stops when all subproblems fail to generate a column with negative (positive) reduced cost in the case of a minimization (maximization) problem or when it reaches the maximum number of iterations.

Parameters:

• restr_master_solve_alg: algorithm to optimize the master LP
• pricing_prob_solve_alg: algorithm to optimize the subproblems
• essential_cut_gen_alg: algorithm to generate essential cuts which is run when the solution of the master LP is integer.

Options:

• max_nb_iterations: maximum number of iterations
• log_print_frequency: display frequency of iterations statistics
• strict_integrality_check: by default (value false) the integrality check in column generation is performed by the mapping procedure from "F. Vanderbeck, Branching in branch-and-price: a generic scheme, Math.Prog. (2011)"; in the case the pricing subproblems are solved by a callback, and some subproblem integer variables are "hidden" from Coluna, the mapping procedure may not be valid, and the integrality should be checked in the "strict" way (explicitly verifying that all columns are integer)

Undocumented parameters are in alpha version.

At each iteration (depending on log_print_frequency), the column generation algorithm can display following statistics.

<it= 90> <et=15.62> <mst= 0.02> <sp= 0.05> <cols= 4> <al= 0.00> <DB=  300.2921> <mlp=  310.3000> <PB=310.3000>

Here are their meanings :

• it stands for the current number of iterations of the algorithm
• et is the elapsed time in seconds since Coluna has started the optimisation
• mst is the time in seconds spent solving the master LP at the current iteration
• sp is the time in seconds spent solving the subproblems at the current iteration
• cols is the number of column generated by the subproblems at the current iteration
• al is the smoothing factor of the stabilisation at the current iteration (alpha version)
• DB is the dual bound of the master LP at the current iteration
• mlp is the objective value of the master LP at the current iteration
• PB is the objective value of the best primal solution found by Coluna at the current iteration
Coluna.Algorithm.ColumnsSetType

Stores a collection of columns.

It contains:

• columns: a vector of GeneratedColumn objects by all pricing subproblems that will be inserted into the master
• subprob_primal_solutions: an object that stores the best columns generated by each pricing subproblem at this iteration.
Coluna.Algorithm.CutCallbacksType
CutCallbacks(
call_robust_facultative = true,
call_robust_essential = true,
tol::Float64 = 1e-6
)

Runs the cut user callbacks attached to a formulation.

Parameters:

• call_robust_facultative: if true, call all the robust facultative cut user callbacks (i.e. user cut callbacks)
• call_robust_essential: if true, call all the robust essential cut user callbacks (i.e. lazy constraint callbacks)
• tol: tolerance used to determine if a cut is violated

See the JuMP documentation for more information about user callbacks and the tutorials in the Coluna documentation for examples of user callbacks.

Coluna.Algorithm.DwPresolveReformType

Stores the presolve-representation of the formulations of the Dantzig-Wolfe reformulation. This datastructure contains:

• representative_master that contains the master formulation expressed with representative variables and pure master variables
• restricted_master that contains the master formulation expressed with pure master variables, master columns, and artificial variables
• dw_sps a dictionary that contains the subproblem formulations.
Coluna.Algorithm.GeneratedColumnType

Solution to a pricing subproblem after a given optimization.

It contains:

• column: the solution stored as a PrimalSolution object
• red_cost: the reduced cost of the column
• min_obj: a boolean indicating if the objective is to minimize or maximize
Coluna.Algorithm.GeneratedCutType

Solution to the separation problem together with its corresponding benders cut.

It contains:

• min_sense: true if it's a minimization problem; false otherwise.
• lhs: the left-hand side of the cut.
• rhs: the right-hand side of the cut.
• dual_sol: an optimal dual solution to the separation problem.
Coluna.Algorithm.MissingPricingDualBoundType
MissingPricingDualBound

Error thrown when the pricing callback does not transmit any dual bound. Make sure you call MOI.submit(model, BD.PricingDualBound(cbdata), db) in your pricing callback.

Coluna.Algorithm.MoiOptimizeType
MoiOptimize(
time_limit = 600
deactivate_artificial_vars = false
enforce_integrality = false
get_dual_bound = true
)

Configuration for an optimizer that calls a subsolver through MathOptInterface.

Parameters:

• time_limit: in seconds
• deactivate_artificial_vars: deactivate all artificial variables of the formulation if equals true
• enforce_integrality: enforce integer variables that are relaxed if equals true
• get_dual_bound: store the dual objective value in the output if equals true
Coluna.Algorithm.MultiplePricingDualBoundsType
MultiplePricingDualBounds

Error thrown when the pricing transmits multiple dual bound. Make sure you call MOI.submit(model, BD.PricingDualBound(cbdata), db) only once in your pricing callback.

Coluna.Algorithm.NodeType

Branch-and-bound node. It stores only local information about the node. Global information about the branch-and-bound belong to the search space object.

Coluna.Algorithm.OptimizationStateMethod
OptimizationState(
form;
termination_status = OPTIMIZE_NOT_CALLED,
ip_primal_bound = nothing,
ip_dual_bound = nothing,
lp_primal_bound = nothing,
lp_dual_bound = nothing,
max_length_ip_primal_sols = 1,
max_length_lp_primal_sols = 1,
max_length_lp_dual_sols = 1,
insert_function_ip_primal_sols = bestbound!,
insert_function_lp_primal_sols = bestbound!,
insert_function_lp_dual_sols = bestbound!
)

A convenient structure to maintain and return solutions and bounds of a formulation form during an optimization process. The termination status is OPTIMIZE_NOT_CALLED by default. You can define the initial incumbent bounds using ip_primal_bound, ip_dual_bound, lp_primal_bound, and lp_primal_bound keyword arguments. Incumbent bounds are set to infinite (according to formulation objective sense) by default. You can store three types of solutions ip_primal_sols, lp_primal_sols, and lp_dual_sols. These solutions are stored in three lists. Keywords max_length_ip_primal_sols, max_length_lp_primal_sols, and max_length_lp_dual_sols let you define the maximum size of the lists. Keywords insert_function_ip_primal_sols, insert_function_lp_primal_sols, and insert_function_lp_dual_sols let you provide a function to define the way you want to insert a new solution in each list. By default, lists are sorted by best bound.

You can also create an OptimizationState from another one :

OptimizationState(
form, source_state, copy_ip_primal_sol, copy_lp_primal_sol
)

It copies the termination status, all the bounds of source_state. If copies the best IP primal solution when copy_ip_primal_sol equals true and the best LP primal solution when copy_lp_primal_sol equals true.

Coluna.Algorithm.PresolveFormulationType

Stores a matrix-representation of the formulation and the mapping between the variables & constraints of the formulation to the row and column of the matrix and components of the vector that represents the formulation.

Coluna.Algorithm.ReducedCostsCalculationHelperType

Extracted information to speed-up calculation of reduced costs of subproblem representatives and pure master variables. We extract from the master the information we need to compute the reduced cost of DW subproblem variables:

• dw_subprob_c contains the perenial cost of DW subproblem representative variables
• dw_subprob_A is a submatrix of the master coefficient matrix that involves only DW subproblem representative variables.

We also extract from the master the information we need to compute the reduced cost of pure master variables:

• pure_master_c contains the perenial cost of pure master variables
• pure_master_A is a submatrix of the master coefficient matrix that involves only pure master variables.

Calculation is c - transpose(A) * master_lp_dual_solution.

This information is given to the generic implementation of the column generation algorithm through methods:

• ColGen.getsubprobvarorigcosts
• ColGen.getorigcoefmatrix
Coluna.Algorithm.RestrMasterLPConquerType
RestrMasterLPConquer(
masterlpalgo = SolveLpForm(
get_ip_primal_sol = true
)
)

Conquer algorithm that solves the master problem using a linear programming solver.

Coluna.Algorithm.RestrictedMasterHeuristicType

The restricted master heuristic enforces integrality of the master column variables and optimizes the master problem restricted to active master column variables using a MIP solver. If the heuristic finds a solution, it checks that this solution does not violate any essential cut.

Coluna.Algorithm.RhsCalculationHelperType

Precompute information to speed-up calculation of right-hand side of benders subproblems. We extract the following information from the subproblems:

• a contains the perenial rhs of all subproblem constraints;
• A is a submatrix of the subproblem coefficient matrix that involves only first stage variables.
Coluna.Algorithm.SepSolSetType

Primal solutions to the separation problems optimized at the current iteration. This is used to build a primal solution.

It contains sols a vector of primal solutions.

Coluna.Algorithm.SingleVarBranchingRuleType
SingleVarBranchingRule

This branching rule allows the divide algorithm to branch on single integer variables. For instance, SingleVarBranchingRule can produce the branching x <= 2 and x >= 3 where x is a scalar integer variable.

Coluna.Algorithm.SolveIpFormType
Coluna.Algorithm.SolveIpForm(
optimizer_id = 1
moi_params = MoiOptimize()
user_params = UserOptimize()
custom_params = CustomOptimize()
)

Solve an optimization problem. This algorithm can call different type of optimizers :

• subsolver interfaced with MathOptInterface to optimize a mixed integer program
• pricing callback defined by the user
• custom optimizer to solve a custom model

You can specify an optimizer using the default_optimizer attribute of Coluna or with the method specify! from BlockDecomposition. If you want to define several optimizers for a given subproblem, you must use specify!:

specify!(subproblem, optimizers = [optimizer1, optimizer2, optimizer3])

Value of optimizer_id is the position of the optimizer you want to use. For example, if optimizer_id is equal to 2, the algorithm will use optimizer2.

By default, the algorihm uses the first optimizer or the default optimizer if no optimizer has been specified through specify!.

Depending on the type of the optimizer chosen, the algorithm will use one the three configurations :

• moi_params for subsolver interfaced with MathOptInterface
• user_params for pricing callbacks
• custom_params for custom solvers

Custom solver is undocumented because alpha.

Coluna.Algorithm.SolveLpFormType
Coluna.Algorithm.SolveLpForm(
get_ip_primal_sol = false,
get_dual_sol = false,
relax_integrality = false,
get_dual_bound = false,
silent = true
)

Solve a linear program stored in a formulation using its first optimizer. This algorithm works only if the optimizer is interfaced with MathOptInterface.

You can define the optimizer using the default_optimizer attribute of Coluna or with the method specify! from BlockDecomposition

Parameters:

• get_ip_primal_sol: update the primal solution of the formulation if equals true
• get_dual_sol: retrieve the dual solution and store it in the ouput if equals true
• relax_integrality: relax integer variables of the formulation before optimization if equals true
• get_dual_bound: store the dual objective value in the output if equals true
• silent: set MOI.Silent() to its value

Undocumented parameters are alpha.

Coluna.Algorithm.StrongBranchingType
StrongBranching(
phases = [],
rules = [Branching.PrioritisedBranchingRule(SingleVarBranchingRule(), 1.0, 1.0)],
selection_criterion = MostFractionalCriterion(),
verbose = true,
int_tol = 1e-6
)

The algorithm that performs a (multi-phase) (strong) branching in a tree search algorithm.

Strong branching is a procedure that heuristically selects a branching constraint that potentially gives the best progress of the dual bound. The procedure selects a collection of branching candidates based on their branching rule and their score. Then, the procedure evaluates the progress of the dual bound in both branches of each branching candidate by solving both potential children using a conquer algorithm. The candidate that has the largest product of dual bound improvements in the branches is chosen to be the branching constraint.

When the dual bound improvement produced by the branching constraint is difficult to compute (e.g. time-consuming in the context of column generation), one can let the branching algorithm quickly estimate the dual bound improvement of each candidate and retain the most promising branching candidates. This is called a phase. The goal is to first evaluate a large number of candidates with a very fast conquer algorithm and retain a certain number of promising ones. Then, over the phases, it evaluates the improvement with a more precise conquer algorithm and restrict the number of retained candidates until only one is left.

Parameters:

Coluna.Algorithm.SubgradientCalculationHelperType

Precompute information to speed-up calculation of subgradient of master variables. We extract from the master follwowing information:

• a contains the perenial rhs of all master constraints except convexity constraints;
• A is a submatrix of the master coefficient matrix that involves only representative of original variables (pure master vars + DW subproblem represtative vars)

Calculation is a - A * (m .* z) where :

• m contains a multiplicity factor for each variable involved in the calculation (lower or upper sp multiplicity depending on variable reduced cost);
• z is the concatenation of the solution to the master (for pure master vars) and pricing subproblems (for DW subproblem represtative vars).

Operation m .* z "mimics" a solution in the original space.

Coluna.Algorithm.SubprobPrimalSolsSetType

Columns generated at the current iteration that forms the "current primal solution". This is used to compute the Lagragian dual bound.

It contains:

• primal_sols a dictionary that maps a formulation id to the best primal solution found by the pricing subproblem associated to this formulation
• improve_master a dictionary that maps a formulation id to a boolean indicating if the best primal solution found by the pricing subproblem associated to this formulation has negative reduced cost

This structure also helps to compute the subgradient of the Lagrangian function.

Coluna.Algorithm.TreeSearchAlgorithmType
Coluna.Algorithm.TreeSearchAlgorithm(
presolvealg = nothing,
conqueralg::AbstractConquerAlgorithm = ColCutGenConquer(),
dividealg::AbstractDivideAlgorithm = Branching(),
explorestrategy::AbstractExploreStrategy = DepthFirstStrategy(),
maxnumnodes = 100000,
opennodeslimit = 100,
timelimit = -1, # -1 means no time limit
opt_atol::Float64 = DEF_OPTIMALITY_ATOL,
opt_rtol::Float64 = DEF_OPTIMALITY_RTOL,
branchingtreefile = "",
jsonfile = "",
print_node_info = true
)

This algorithm is a branch and bound that uses a search tree to optimize the reformulation. At each node in the tree, it applies conqueralg to evaluate the node and improve the bounds, dividealg to generate branching constraints, and explorestrategy to select the next node to treat. Optionally, the presolvealg is run in the beginning to preprocess the formulation.

The three main elements of the algorithm are:

• the conquer strategy (conqueralg): evaluation of the problem at a node of the Branch-and-Bound tree. Depending on the type of decomposition used ahead of the Branch-and-Bound, you can use either Column Generation (if your problem is decomposed following Dantzig-Wolfe transformation) and/or Cut Generation (for Dantzig-Wolfe and Benders decompositions).
• the branching strategy (dividealg): how to create new branches i.e. how to divide the search space
• the explore strategy (explorestrategy): the evaluation order of your nodes

Parameters:

• maxnumnodes : maximum number of nodes explored by the algorithm
• opennodeslimit : maximum number of nodes waiting to be explored
• timelimit : time limit in seconds of the algorithm
• opt_atol : optimality absolute tolerance (alpha)
• opt_rtol : optimality relative tolerance (alpha)

Options:

• branchingtreefile : name of the file in which the algorithm writes an overview of the branching tree
• jsonfile : name of the file in which the algorithm writes the solution in JSON format
• print_node_info : log the tree into the console

Warning: if you set a name for the branchingtreefile AND the jsonfile, the algorithm will only write in the json file.

Coluna.Algorithm.UserOptimizeType
UserOptimize(
max_nb_ip_primal_sols = 50
)

Configuration for an optimizer that calls a pricing callback to solve the problem.

Parameters:

• max_nb_ip_primal_sols: maximum number of solutions returned by the callback kept
Coluna.Algorithm._get_costs_and_coeffsMethod

Function var_duty_func(form, var_id, var) returns true if we want to keep the variable var_id; false otherwise. Same for constr_duty_func(form, constr_id, constr).

Coluna.Algorithm._subprob_var_contribMethod

When we use a smoothed dual solution, we need to recompute the reduced cost of the subproblem variables using the non-smoothed dual solution (out point). This reduced cost is stored in the context (field sp_var_redcosts) and we use it to compute the contribution of the subproblem variables.

Coluna.Algorithm.add_ip_primal_sol!Method
add_ip_primal_sol!(optstate, sol)
add_ip_primal_sols!(optstate, sols...)

Add the solution sol at the end of the solution list of opstate, sort the solution list, remove the worst solution if the solution list size is exceded, and update the incumbent bound if the solution is better.

Similar methods :

add_lp_primal_sol!(optstate, sol)
add_lp_dual_sol!(optstate, sol)
Coluna.Algorithm.check_alg_parametersMethod
check_alg_parameters(top_algo, reform) -> Vector{Tuple{Symbol, AbstractAlgorithm, Any}}

Checks the consistency of the parameters of the top algorithm and its children algorithms. Returns a vector of tuples (name of the parameter, algorithm, value of the parameter) that lists all the inconsistencies found in the algorithms tree.

Coluna.Algorithm.create_recordsMethod
create_records(reformulation) -> Records

Methods to create records of all storage units of a reformulation and the formulations handled by the reformulation.

Coluna.Algorithm.empty_ip_primal_sols!Method
empty_ip_primal_sols!(optstate)

Remove all IP primal solutions from optstate.

Similar methods :

empty_lp_primal_sols!(optstate)
empty_lp_dual_sols!(optstate)
Coluna.Algorithm.get_child_algorithmsMethod
get_child_algorithms(algo, model) -> Dict{String, Tuple{AbstractAlgorithm, AbstractModel}}

Every algorithm should communicate its child algorithms and the model to which each child algorithm is applied. It should returns a dictionary where the keys are the names of the child algorithms and the values are the algorithm parameters and the model to which the algorithm is applied.

By default, get_child_algorithms returns an empty dictionary.

Coluna.Algorithm.get_units_usageMethod
get_units_usage(algo, model) -> Tuple{AbstractModel, UnitType, UnitPermission}[]

Every algorithm should communicate the storage units it uses (so that these units are created in the beginning) and the usage mode (read only or read-and-write). Usage mode is needed for in order to restore units before running a worker algorithm.

Coluna.Algorithm.ip_gap_closedMethod
ip_gap_closed(optstate; atol = Coluna.DEF_OPTIMALITY_ATOL, rtol = Coluna.DEF_OPTIMALITY_RTOL)

Return true if the gap between the best primal and dual bounds of the integer program is closed given optimality tolerances.

Coluna.Algorithm.is_prunedMethod

Returns true if the current node should not be explored i.e. if its local dual bound inherited from its parent is worst than a primal bound of the search space.

Coluna.Algorithm.lp_gap_closedMethod
lp_gap_closed(optstate; atol = Coluna.DEF_OPTIMALITY_ATOL, rtol = Coluna.DEF_OPTIMALITY_RTOL)

Return true if the gap between the best primal and dual bounds of the linear program is closed given optimality tolerances.

Coluna.Algorithm.node_change!Method

Methods to perform operations before the tree search algorithm evaluates a node (current). This is useful to restore the state of the formulation for instance.

Coluna.Algorithm.restore_from_records!Method
restore_from_records!(units_used::UnitsUsage, records::Records)

Method to restore storage units from reformulations and formulations given a set of records stored in an object of type Records.

Coluna.Algorithm.run_colcutgen!Method

Runs several rounds of column and cut generation. Returns false if the column generation returns false or time limit is reached. Returns true if the conquer algorithm continues.

Coluna.Algorithm.run_colgen!Method

Runs a column generation algorithm and updates the optimization state of the node with the result of the column generation. Returns false if the node is infeasible, subsolver time limit is reached, or node gap is closed; true if the conquer algorithm continues.

Coluna.Algorithm.run_preprocessing!Method

Runs the preprocessing algorithm. Returns true if conquer algorithm should continue; false otherwise (in the case where preprocessing finds the formulation infeasible).

Coluna.Algorithm.set_ip_primal_sol!Method
set_ip_primal_sol!(optstate, sol)

Empties the list of solutions and add solution sol in the list. The incumbent bound is not updated even if the value of the solution is better.

Similar methods :

set_lp_primal_sol!(optstate, sol)
set_lp_dual_sol!(optstate, sol)
Coluna.Algorithm.update_ip_primal_sol!Method
update_ip_primal_sol!(optstate, sol)

Add the solution sol in the solutions list of optstate if and only if the value of the solution is better than the incumbent. The solution is inserted in the list by the method defined in insert_function_ip_primal_sols field of OptimizationState. If the maximum length of the list is reached, the solution located at the end of the list is removed.

Similar methods :

update_lp_primal_sol!(optstate, sol)
update_lp_dual_sol!(optstate, sol)
Coluna.MathProg.AbstractFormulationType
AbstractFormulation

Formulation is a mathematical representation of a problem (model of a problem). A problem may have different formulations. We may rename "formulation" to "model" after. Different algorithms may be applied to a formulation. A formulation should contain a dictionary of storage units used by algorithms. A formulation contains one storage unit per storage unit type used by algorithms.

Coluna.MathProg.DualSolutionMethod
DualSolution(
form::AbstractFormulation,
constrids::Vector{ConstrId},
constrvals::Vector{Float64},
varids::Vector{VarId},
varvals::Vector{Float64},
varactivebounds::Vector{ActiveBound},
cost::Float64,
status::SolutionStatus;
custom_data::Union{Nothing, BlockDecomposition.AbstractColumnData} = nothing
)

Create a dual solution to the formulation form of cost cost and status status. It contains constrids the set of ids of the constraints and constrvals the values of the constraints (constrvals[i] is dual value of constrids[i]). It also contains varvals[i] the dual values of the bound constraint varactivebounds[i] of the variables varids (also known as the reduced cost).

The user can attach to the dual solution a customized representation custom_data.

Coluna.MathProg.DutyType
Duty{Variable}

Duties of a variable are tree-structured values wrapped in Duty{Variable} instances. Leaves are concret duties of a variable, intermediate nodes are duties representing families of duties, and the root node is a Duty{Variable} with value 1.

Duty{Constraint}

It works like Duty{Variable}.

Examples

If a duty Duty1 inherits from Duty2, then

julia> Duty1 <= Duty2
true
Coluna.MathProg.FormulationBufferType

A FormulationBuffer stores all changes done to a formulation since last call to sync_solver!. When function sync_solver! is called, the optimizer is synched with all changes in FormulationBuffer

Warning : You should not pass formulation changes straight to its optimizer. Changes must be always buffered.

Coluna.MathProg.IdType

Coluna identifier of a Variable or a Constraint.

The identifier is a subtype of Integer so we can use it as index of sparse arrays. It behaves like an integer (field uid) with additional information (other fields).

It is composed by the following ids:

1. uid: unique id that is global to the Coluna instance (the integer)
2. origin_form_uid: unique id of the formulation where it was generated
3. assigned_form_uid: unique id of the formulation where it is assigned in the reformulation process

For a JuMP variable/constraint the origin_form_uid is the original formulation while the assigned_form_uid is the subproblem formulation for a pure subproblem variable/constraint and the master for a pure master variable/constraint.

For a variable/constraint generated during optimization, the origin_form_uid is the id of the formulation where it was created. For instance, the origin formulation of a master column is the subproblem for which the column is a solution and its assigned formulation is the master.

Coluna.MathProg.MoiOptimizerType
MoiOptimizer <: AbstractOptimizer

Wrapper that is used when the optimizer of a formulation is an MOI.AbstractOptimizer, thus inheriting MOI functionalities.

Coluna.MathProg.NoOptimizerType
NoOptimizer <: AbstractOptimizer

Wrapper when no optimizer is assigned to a formulation. Basic algorithms that call an optimizer to optimize a formulation won't work.

Coluna.MathProg.PrimalSolutionMethod
PrimalSolution(
form::AbstractFormulation,
varids::Vector{VarId},
varvals::Vector{Float64},
cost::Float64,
status::SolutionStatus;
custom_data::Union{Nothing, BlockDecomposition.AbstractCustomVarData} = nothing
)

Create a primal solution to the formulation form of cost cost and status status. The representations of the soslution is varids the set of the ids of the variables and varvals the values of the variables (varvals[i] is value of variable varids[i]).

The user can also attach to the primal solution a customized representation custom_data.

Coluna.MathProg.ReformulationMethod

Reformulation is a representation of a formulation which is solved by Coluna using a decomposition approach.

Reformulation(env, parent, master, dw_pricing_subprs, benders_sep_subprs)

Constructs a Reformulation where:

• env is the Coluna environment;
• parent is the parent formulation (a Formulation or a Reformulation) (original

formulation for the classic decomposition);

• master is the formulation of the master problem;
• dw_pricing_subprs is a Dict{FormId, Formulation} containing all Dantzig-Wolfe pricing

subproblems of the reformulation;

• benders_sep_subprs is a Dict{FormId, Formulation} containing all Benders separation

subproblems of the reformulation.

Coluna.MathProg.UserOptimizerType
UserOptimizer <: AbstractOptimizer

Wrap a julia function that acts like the optimizer of a formulation. It is for example the function used as a pricing callback.

Base.delete!Method
delete!(formulation, varconstr)
delete!(formulation, varconstrid)

Delete a variable or a constraint from a formulation.

Base.haskeyMethod
haskey(formulation, id) -> Bool

Returns true if formulation has a variable or a constraint with given id.

Coluna.MathProg.DualBoundMethod
DualBound(formulation)
DualBound(formulation, value)
DualBound(formulation, db)

Create a new dual bound for the formulation formulation. The value of the dual bound is infinity if you do not specify any initial value.

Coluna.MathProg.PrimalBoundMethod
PrimalBound(formulation)
PrimalBound(formulation, value)
PrimalBound(formualtion, pb)

Create a new primal bound for the formulation formulation. The value of the primal bound is infinity if you do not specify any initial value.

Coluna.MathProg.activate!Method
activate!(formulation, varconstrid)
activate!(formulation, varconstr)

Activate a variable or a constraint in a formulation.

activate!(formulation, function)

It is also possible to activate variables and constraints of a formulation such that function(varconstrid) returns true.

Coluna.MathProg.add_to_partial_solution!Function
add_to_partial_solution!(formulation, varid, value)

Set the minimal value that the variable with id varid takes into the optimal solution. If the variable is already in the partial solution, the value cumulates with the current. If the cumulative value is 0, the variable is removed from the partial solution.

Warning: by default, there is no propagation, no change on variable bounds, you must call the presolve algorithm.

Coluna.MathProg.computecoeffMethod
computecoeff(var_custom_data, constr_custom_data) -> Float64

Dispatches on the type of custom data attached to the variable and the constraint to compute the coefficient of the variable in the constraint.

Coluna.MathProg.create_formulation!Method

A Formulation stores a mixed-integer linear program.

create_formulation!(
env::Coluna.Env,
duty::AbstractFormDuty;
parent_formulation = nothing,
obj_sense::Type{<:Coluna.AbstractSense} = MinSense
)

Creates a new formulation in the Coluna's environment env. Arguments are duty that contains specific information related to the duty of the formulation, parent_formulation that is the parent formulation (master for a subproblem, reformulation for a master, nothing by default), and obj_sense the sense of the objective function (MinSense or MaxSense).

Coluna.MathProg.deactivate!Method
deactivate!(formulation, varconstrid)
deactivate!(formulation, varconstr)

Deactivate a variable or a constraint in a formulation.

deactivate!(formulation, function)

It is also possible to deactivate variables and constraints such that function(varconstrid) returns true.

Coluna.MathProg.get_column_from_poolMethod
get_column_from_pool(primal_sol)

Returns the var_id of the master column that represents the primal solution primal_sol to a Dantzig-Wolfe subproblem if the primal solution exists in the pool of solutions to the subproblem; nothing otherwise.

Coluna.MathProg.get_dw_pricing_spsMethod
get_dw_pricing_sps(reformulation)

Return a Dict{FormId, AbstractModel} containing all Dabtzig-Wolfe pricing subproblems of the reformulation.

Coluna.MathProg.get_optimization_targetMethod

If the original formulation is not reformulated, it means that the user did not provide a way to decompose the model. In such a case, Coluna will call the subsolver to optimize the original formulation.

Coluna.MathProg.getconstrMethod
getconstr(formulation, constrid) -> Constraint

Returns the constraint with given constrid that belongs to formulation.

Coluna.MathProg.getcurcostMethod
getcurcost(formulation, variable)
getcurcost(formulation, varid)

Return the current cost of the variable in the formulation.

Coluna.MathProg.getcurincvalMethod
getcurincval(formulation, varconstrid)
getcurincval(formulation, varconstr)

Return the current incumbent value of a variable or a constraint in a formulation.

Coluna.MathProg.getcurkindMethod
getcurkind(formulation, variable)
getcurkind(formulation, varid)

Return the current kind of a variable in a formulation.

Coluna.MathProg.getcurlbMethod
getcurlb(formulation, varid)
getcurlb(formulation, var)

Return the current lower bound of a variable in a formulation.

Coluna.MathProg.getcurrhsMethod
getcurrhs(formulation, constraint)
getcurrhs(formulation, constrid)

Return the current right-hand side of a constraint in a formulation.

Coluna.MathProg.getcursenseMethod
getcursense(formulation, varconstr)
getcursense(formulation, varconstrid)

Return the current sense of a variable or a constraint in a formulation. The current sense of a variable depends on its current bounds.

Coluna.MathProg.getcurubMethod
getcurub(formulation, varid)
getcurub(formulation, var)

Return the current upper bound of a variable in a formulation.

Coluna.MathProg.getcustomdataMethod
getcustomdata(formulation, var)
getcustomdata(formulation, varid)
getcustomdata(formulation, constr)
getcustomdata(formulation, constrid)

Return the custom data of a variable or a constraint in a formulation.

Coluna.MathProg.getelemMethod
getelem(form, varid) -> Variable
getelem(form, constrid) -> Constraint

Return the element of formulation form that has a given id.

Coluna.MathProg.getnameMethod
getname(formulation, varconstr)
getname(formulation, varconstrid)

Return the name of a variable or a constraint in a formulation.

Coluna.MathProg.getobjsenseMethod
getobjsense(reformulation)

Return the objective sense of the master problem of the reformulation. If the master problem has not been defined, it throws an error.

Coluna.MathProg.getparentMethod
getparent(form) -> AbstractFormulation

Returns the parent formulation of a given formulation. This is usually:

• the master for a subproblem
• the reformulation for the master
Coluna.MathProg.getperencostMethod
getperencost(formulation, variable)
getperencost(formulation, varid)

Return the cost as defined by the user of a variable in a formulation.

Coluna.MathProg.getperenincvalMethod
getperenincval(formulation, varconstrid)
getperenincval(formulation, varconstr)

Return the incumbent value as defined by the user of a variable or a constraint in a formulation. The incumbent value is the primal value associated to a variable or the dual value associated to a constraint.

Coluna.MathProg.getperenkindMethod
getperenkind(formulation, varconstr)
getperenkind(formulation, varconstrid)

Return the kind as defined by the user of a variable or a constraint in a formulation.

Kinds of variable (enum VarKind) are Continuous, Binary, or Integ.

Kinds of a constraint (enum ConstrKind) are :

• Essential when the constraint structures the problem
• Facultative when the constraint does not structure the problem
• SubSystem (to do)

The kind of a constraint cannot change.

Coluna.MathProg.getperenlbMethod
getperenlb(formulation, varid)
getperenlb(formulation, var)

Return the lower bound as defined by the user of a variable in a formulation.

Coluna.MathProg.getperenrhsMethod
getperenrhs(formulation, constraint)
getperenrhs(formulation, constrid)

Return the right-hand side as defined by the user of a constraint in a formulation.

Coluna.MathProg.getperensenseMethod
getperensense(formulation, varconstr)
getperensense(formulation, varconstrid)

Return the sense as defined by the user of a variable or a constraint in a formulation.

Senses or a variable are (enum VarSense) Positive, Negative, and Free. Senses or a constraint are (enum ConstrSense) Greater, Less, and Equal.

The perennial sense of a variable depends on its perennial bounds.

Coluna.MathProg.getperenubMethod
getperenub(formulation, varid)
getperenub(formulation, var)

Return the upper bound as defined by the user of a variable in a formulation.

Coluna.MathProg.getvarMethod
getvar(formulation, varid) -> Variable

Returns the variable with given varid that belongs to formulation.

Coluna.MathProg.in_partial_solMethod
in_partial_sol(form, varid)
in_partial_sol(form, variable)

Return true if the variable is in the partial solution; false otherwise.

Coluna.MathProg.insert_column!Method
insert_column!(master_form, primal_sol, name)

Inserts the primal solution primal_sol to a Dantzig-Wolfe subproblem into the master as a column.

Returns var_id the id of the column variable in the master formulation.

Warning: this methods does not check if the column already exists in the pool.

Coluna.MathProg.iscuractiveMethod
iscuractive(formulation, varconstrid)
iscuractive(formulation, varconstr)

Return true if the variable or the constraint is currently active; false otherwise.

Coluna.MathProg.isexplicitMethod
isexplicit(formulation, varconstr)
isexplicit(formulation, varconstrid)

Return true if a variable or a constraint is explicit in a formulation; false otherwise.

Coluna.MathProg.isperenactiveMethod
isperenactive(formulation, varconstrid)
isperenactive(formulation, varconstr)

Return true if the variable or the constraint is active in the formulation; false otherwise. A variable (or a constraint) is active if it is used in the formulation. You can fake the deletion of the variable by deativate it. This allows you to keep the variable if you want to reactivate it later.

Coluna.MathProg.setconstr!Method
setconstr!(
formulation, name, duty;
rhs = 0.0,
kind = Essential,
sense = Greater,
is_active = true,
is_explicit = true,
members = nothing,
loc_art_var_abs_cost = 0.0,
)

Create a new constraint that has name name and duty duty in the formulation formulation. Following keyword arguments allow the user to set additional information about the new constraint :

• rhs: right-hand side of the constraint
• kind: kind which can be Essential or Facultative
• sense: sense which can be Greater, Less, or Equal
• is_active: true if the constraint is used in the formulation, false otherwise
• is_explicit: true if the constraint structures the formulation, false otherwise
• members: a dictionary Dict{VarId, Float64} that contains the coefficients of the variables of the formulation in the new constraint (default coefficient is 0).
• loc_art_var_abs_cost: absolute cost of the artificial variables of the constraint
Coluna.MathProg.setcurcost!Method
setcurcost!(formulation, varid, cost::Float64)
setcurcost!(formulation, variable, cost::Float64)

Set the current cost of variable in the formulation. If the variable is active and explicit, this change is buffered before application to the subsolver.

Coluna.MathProg.setcurkind!Method
setcurkind!(formulation, variable, kind::VarKind)
setcurkind!(formulation, varid, kind::VarKind)

Set the current kind of a variable in a formulation. If the variable is active and explicit, this change is buffered before application to the subsolver

Coluna.MathProg.setcurlb!Method
setcurlb!(formulation, varid, lb::Float64)
setcurlb!(formulation, var, lb::Float64)

Set the current lower bound of a variable in a formulation. If the variable is active and explicit, change is buffered before application to the subsolver. If the variable had fixed value, it unfixes the variable.

Coluna.MathProg.setcurrhs!Method
setcurrhs(formulation, constraint, rhs::Float64)
setcurrhs(formulation, constrid, rhs::Float64)

Set the current right-hand side of a constraint in a formulation. If the constraint is active and explicit, this change is buffered before application to the subsolver.

Warning : if you change the rhs of a single variable constraint, make sure that you perform bound propagation before calling the subsolver of the formulation.

Coluna.MathProg.setcursense!Method
setcursense!(formulation, constr, sense::ConstrSense)
setcursense!(formulation, constrid, sense::ConstrSense)

Set the current sense of a constraint in a formulation.

This method is not applicable to variables because the sense of a variable depends on its bounds.

Warning : if you set the sense of a single var constraint, make sure you perform bound propagation before calling the subsolver of the formulation.

Coluna.MathProg.setcurub!Method
setcurub!(formulation, varid, ub::Float64)
setcurub!(formulation, var, ub::Float64)

Set the current upper bound of a variable in a formulation. If the variable is active and explicit, change is buffered before application to the subsolver. If the variable had fixed value, it unfixes the variable.

Coluna.MathProg.setperencost!Method
setperencost!(formulation, variable, cost)
setperencost!(formulation, varid, cost)

Set the perennial cost of a variable and then propagate change to the current cost of the variable.

Coluna.MathProg.setperenkind!Method
setperenkind!(formulation, variable, kind)
setperenkind!(formulation, varid, kind)

Set the perennial kind of a variable in a formulation. This change is then propagated to the current kind of the variable.

Coluna.MathProg.setperenlb!Method
setperenlb!(formulation, var, rhs)

Set the perennial lower bound of a variable in a formulation. Change is propagated to the current lower bound of the variable.

Coluna.MathProg.setperenrhs!Method
setperenrhs!(formulation, constr, rhs)
setperenrhs!(formulation, constrid, rhs)

Set the perennial rhs of a constraint in a formulation. Change is propagated to the current rhs of the constraint.

Coluna.MathProg.setperensense!Method
setperensense!(form, constr, sense)
setperensense!(form, constrid, sense)

Set the perennial sense of a constraint in a formulation. Change is propagated to the current sense of the constraint.

Warning : if you set the sense of a single var constraint, make sure you perform bound propagation before calling the subsolver of the formulation.

Coluna.MathProg.setperenub!Method
setperenub!(formulation, var, rhs)

Set the perennial upper bound of a variable in a formulation. Change is propagated to the current upper bound of the variable.

Coluna.MathProg.setvar!Method
setvar!(
formulation, name, duty;
cost = 0.0,
lb = -Inf,
ub = Inf,
kind = Continuous,
is_active = true,
is_explicit = true,
members = nothing,
)

Create a new variable that has name name and duty duty in the formulation formulation.

Following keyword arguments allow the user to set additional information about the new variable:

• cost: cost of the variable in the objective function
• lb: lower bound of the variable
• ub: upper bound of the variable
• kind: kind which can be Continuous, Binary or Integ
• is_active: true if the variable is used in the formulation, false otherwise
• is_explicit: true if the variable takes part to the formulation, false otherwise (e.g. a variable used as a shortcut for calculation purposes)
• members: a dictionary Dict{ConstrId, Float64} that contains the coefficients of the new variable in the constraints of the formulation (default coefficient is 0).
Coluna.ColGen.AbstractColGenContextType

Supertype for the objects to which belongs the implementation of the column generation and that stores any kind of information during the execution of the column generation algorithm.

IMPORTANT: implementation of the column generation mainly depends on the context type.

Coluna.ColGen.AbstractPricingStrategyType

A pricing strategy defines how we iterate on pricing subproblems. A default pricing strategy consists in iterating on all pricing subproblems.

Basically, this object is used like this:

    pricing_strategy = ColGen.get_pricing_strategy(ctx, phase)
next = ColGen.pricing_strategy_iterate(pricing_strategy)
while !isnothing(next)
(sp_id, sp_to_solve), state = next
# Solve the subproblem sp_to_solve.
next = ColGen.pricing_strategy_iterate(pricing_strategy, state)
end
Coluna.ColGen.after_colgen_iterationMethod

Placeholder method called after the column generation iteration. Does nothing by default but can be redefined to print some informations for instance. We strongly advise users against the use of this method to modify the context or the reformulation.

Coluna.ColGen.before_colgen_iterationMethod

Placeholder method called before the column generation iteration. Does nothing by default but can be redefined to print some informations for instance. We strongly advise users against the use of this method to modify the context or the reformulation.

Coluna.ColGen.compute_dual_boundMethod
compute_dual_bound(ctx, phase, master_lp_obj_val, master_dbs, generated_columns, mast_dual_sol) -> Float64

Caculates the dual bound at a given iteration of column generation. The dual bound is composed of:

• master_lp_obj_val: objective value of the master LP problem
• master_dbs: dual values of the pricing subproblems
• the contribution of the master convexity constraints that you should compute from mast_dual_sol.
Coluna.ColGen.decrease_stageMethod

Returns the next stage involving a "more exact solver" than the current one. Returns nothing if the algorithm has already reached the exact phase (last phase).

Coluna.ColGen.get_dual_boundMethod

Returns dual bound of the pricing subproblem; nothing if no dual bound is available and the initial dual bound returned by compute_sp_init_db will be used to compute the master dual bound.

Coluna.ColGen.get_primal_boundMethod

Returns primal bound of the pricing subproblem; nothing if no primal bound is available and the initial dual bound returned by compute_sp_init_pb will be used to compute the pseudo dual bound.

Coluna.ColGen.insert_columns!Method

Inserts columns into the master. Returns the number of columns inserted. Implementation is responsible for checking if the column must be inserted and warn the user if something unexpected happens.

Coluna.ColGen.new_iteration_outputMethod
new_iteration_output(::Type{<:AbstractColGenIterationOutput}, args...) -> AbstractColGenIterationOutput

Arguments (i.e. arg...) of this function are the following:

• min_sense: true if the objective is a minimization function; false otherwise
• mlp: the optimal solution value of the master LP
• db: the Lagrangian dual bound
• nb_new_cols: the number of columns inserted into the master
• new_cut_in_master: true if valid inequalities or new constraints added into the master; false otherwise
• infeasible_master: true if the master is proven infeasible; false otherwise
• unbounded_master: true if the master is unbounded; false otherwise
• infeasible_subproblem: true if a pricing subproblem is proven infeasible; false otherwise
• unbounded_subproblem: true if a pricing subproblem is unbounded; false otherwise
• time_limit_reached: true if time limit is reached; false otherwise
• master_primal_sol: the primal master LP solution
• ip_primal_sol: the incumbent primal master solution
• dual_sol: the dual master LP solution
Coluna.ColGen.new_outputMethod
new_output(OutputType, colgen_phase_output) -> OutputType

Returns the column generation output where colgen_phase_output is the output of the last column generation phase executed.

Coluna.ColGen.new_phase_outputMethod
new_phase_output(OutputType, min_sense, phase, stage, colgen_iter_output, iter, inc_dual_bound) -> OutputType

Returns the column generation phase output.

Arguments of this function are:

• OutputType: the type of the column generation phase output
• min_sense: true if it is a minimization problem; false otherwise
• phase: the current column generation phase
• stage: the current column generation stage
• col_gen_iter_output: the last column generation iteration output
• iter: the last iteration number
• inc_dual_bound: the current incumbent dual bound
Coluna.ColGen.optimize_master_lp_problem!Method
optimize_master_lp_problem!(master, context, env) -> MasterResult

Returns an instance of a custom object MasterResult that implements the following methods:

• get_obj_val: objective value of the master (mandatory)
• get_primal_sol: primal solution to the master (optional)
• get_dual_sol: dual solution to the master (mandatory otherwise column generation stops)

It should at least return a dual solution (obtained with LP optimization or subgradient) otherwise column generation cannot continue.

Coluna.ColGen.optimize_pricing_problem!Method
optimize_pricing_problem!(ctx, sp, env, optimizer, mast_dual_sol) -> PricingResult

Returns a custom object PricingResult that must implement the following functions:

• get_primal_sols: array of primal solution to the pricing subproblem
• get_primal_bound: best reduced cost (optional ?)
• get_dual_bound: dual bound of the pricing subproblem (used to compute the master dual bound)
• master_dual_sol: dual solution $\pi^{\text{out}}$ to the master problem used to compute the real reduced cost of the column when stabilization is active
Coluna.ColGen.pricing_strategy_iterateMethod
pricing_strategy_iterate(pricing_strategy) -> ((sp_id, sp_to_solve), state)
pricing_strategy_iterate(pricing_strategy, state) -> ((sp_id, sp_to_solve), state)

Returns an iterator with the first pricing subproblem that must be optimized. The next subproblem is returned by a call to Base.iterate using the information provided by this method.

Coluna.ColGen.push_in_set!Method

Pushes the column in the set of columns generated at a given iteration of the column generation algorithm. Columns stored in the set will then be considered for insertion in the master problem. Returns true if column was inserted in the set, false otherwise.

Coluna.ColGen.run!Method
run!(ctx, env, ip_primal_sol; iter = 1) -> AbstractColGenOutput

Runs the column generation algorithm.

Arguments are:

• ctx: column generation context
• env: Coluna environment
• ip_primal_sol: current best primal solution to the master problem
• iter: iteration number (default: 1)

This function is responsible for initializing the column generation context, the reformulation, and the stabilization. We iterate on the loop each time the phase or the stage changes.

Coluna.ColGen.run_colgen_iteration!Method
run_colgen_iteration!(context, phase, stage, env, ip_primal_sol, stab) -> AbstractColGenIterationOutput

Runs an iteration of column generation.

Arguments are:

• context: column generation context
• phase: current column generation phase
• stage: current column generation stage
• env: Coluna environment
• ip_primal_sol: current best primal solution to the master problem
• stab: stabilization
Coluna.ColGen.run_colgen_phase!Method
run_colgen_phase!(ctx, phase, stage, env, ip_primal_sol, stab; iter = 1) -> AbstractColGenPhaseOutput

Runs a phase of the column generation algorithm.

Arguments are:

• ctx: column generation context
• phase: current column generation phase
• stage: current column generation stage
• env: Coluna environment
• ip_primal_sol: current best primal solution to the master problem
• stab: stabilization
• iter: iteration number (default: 1)

This function is responsible for running the column generation iterations until the phase is finished.

Coluna.ColGen.set_of_columnsMethod

Returns an empty container that will store all the columns generated by the pricing problems during an iteration of the column generation algorithm. One must be able to iterate on this container to insert the columns in the master problem.

Coluna.ColGen.update_stabilization_after_iter!Method

Updates stabilization after an iteration of the column generation algorithm. Arguments:

• stab is the stabilization data structure
• ctx is the column generation context
• master is the master problem
• generated_columns is the set of generated columns
• mast_dual_sol is the dual solution to the master problem
Coluna.ColGen.update_stabilization_after_master_optim!Method
update_stabilization_after_master_optim!(stab, phase, mast_dual_sol) -> Bool

Update stabilization after master optimization where mast_dual_sol is the dual solution to the master problem. Returns true if the stabilization will change the dual solution used for the pricing in the current column generation iteration, false otherwise.

Coluna.ColGen.update_stabilization_after_pricing_optim!Method

Updates stabilization after pricing optimization where:

• mast_dual_sol is the dual solution to the master problem
• pseudo_db is the pseudo dual bound of the problem after optimization of the pricing problems
• smooth_dual_sol is the current smoothed dual solution
Coluna.AlgoAPI.AbstractAlgorithmType

Supertype for algorithms parameters. Data structures that inherit from this type are intented for the users. The convention is to define the data structure together with a constructor that contains only kw args.

For instance:

    struct MyAlgorithmParams <: AbstractAlgorithmParams
param1::Int
param2::Int
MyAlgorithmParams(; param1::Int = 1, param2::Int = 2) = new(param1, param2)
end
Coluna.AlgoAPI.change_model_stateMethod

Returns true if the algorithm will perform changes on the formulation that must be reverted at the end of the execution of the algorithm; false otherwise.

Coluna.AlgoAPI.ColunaBase.SolutionMethod

Solution is an internal data structure of Coluna and should not be used in algorithms. See MathProg.PrimalSolution & MathProg.DualSolution instead.

Solution(
model::AbstractModel,
decisions::Vector,
values::Vector,
solution_value::Float64,
status::SolutionStatus
)

Create a solution to the model. Other arguments are:

• decisions is a vector with the index of each decision.
• values is a vector with the values for each decision.
• solution_value is the value of the solution.
• status is the solution status.
Coluna.AlgoAPI.ColunaBase.SolutionStatusType
SolutionStatus

Description of the solution statuses:

• FEASIBLE_SOL : the solution is feasible
• INFEASIBLE_SOL : the solution is not feasible

If there is no solution or if we don't have information about the solution, the solution status should be :

• UNKNOWN_SOLUTION_STATUS
Coluna.AlgoAPI.ColunaBase.TerminationStatusType
TerminationStatus

Theses statuses are the possible reasons why an algorithm stopped the optimization. When a subsolver is called through MOI, the MOI TerminationStatusCode is translated into a Coluna TerminationStatus.

Description of the termination statuses:

• OPTIMAL : the algorithm found a global optimal solution given the optimality tolerance
• INFEASIBLE : the algorithm proved infeasibility
• UNBOUNDED : the algorithm proved unboundedness
• TIME_LIMIT : the algorithm stopped because of the time limit
• NODE_LIMIT : the branch-and-bound based algorithm stopped due to the node limit
• OTHER_LIMIT : the algorithm stopped because of a limit that is neither the time limit

nor the node limit

If the algorithm has not been called, the default value of the termination status should be:

• OPTIMIZE_NOT_CALLED

If the conversion of a MOI.TerminationStatusCode returns UNCOVERED_TERMINATION_STATUS, Coluna should stop because it enters in an undefined behavior.

Coluna.AlgoAPI.ColunaBase.convert_statusMethod
convert_status(status::MOI.TerminationStatusCode) -> Coluna.TerminationStatus
convert_status(status::Coluna.TerminationStatus) -> MOI.TerminationStatusCode
convert_status(status::MOI.ResultStatusCode) -> Coluna.SolutionStatus
convert_status(status::Coluna.SolutionStatus) -> MOI.ResultStatusCode

Convert a termination or solution status of a given type to the corresponding status in another type. This method is used to communicate between Coluna and MathOptInterface.

Coluna.AlgoAPI.ColunaBase.diffMethod
diff(pb, db)
diff(db, pb)

Distance between a primal bound and a dual bound that have the same objective sense. Distance is non-positive if dual bound reached primal bound.

Coluna.AlgoAPI.ColunaBase.isbetterMethod
isbetter(b1, b2)

Returns true if bound b1 is better than bound b2. The function take into account the space (primal or dual) and the objective sense (min, max) of the bounds.

Coluna.AlgoAPI.ColunaBase.printboundsFunction
printbounds(db, pb [, io])

Prints the lower and upper bound according to the objective sense.

Can receive io::IO as an input, to eventually output the print to a file or buffer.

Coluna.AlgoAPI.ColunaBase.@nestedenumMacro
@nestedenum block_expression

Create a NestedEnum subtype such as :

Example

DocTestSetup = quote
using Coluna
end
Coluna.ColunaBase.@nestedenum begin
TypeOfItem
ItemA <= TypeOfItem
ChildA1 <= ItemA
GrandChildA11 <= ChildA1
GrandChildA12 <= ChildA1
ChildA2 <= ItemA
ItemB <= TypeOfItem
ItemC <= TypeOfItem
end

# output


Create a nested enumeration with items ItemA, ChildA1, ChildA2, GrandChildA11, GrandChildA12, ItemB, and ItemC of type TypeOfItem. The operator <= indicates the parent of the item.

julia> GrandChildA11 <= ItemA
true
julia> GrandChildA11 <= ItemC
false
DocTestSetup = nothing
Coluna.ParamsType
Coluna.Params(
solver = Coluna.Algorithm.TreeSearchAlgorithm(),
global_art_var_cost = 10e6,
local_art_var_cost = 10e4
)

Parameters of Coluna :

• solver is the algorithm used to optimize the reformulation.
• global_art_var_cost is the cost of the global artificial variables in the master
• local_art_var_cost is the cost of the local artificial variables in the master
Coluna.Branching.AbstractSelectionCriterionType

Supertype of selection criteria of branching candidates.

A selection criterion provides a way to keep only the most promising branching candidates. To create a new selection criterion, one needs to create a subtype of AbstractSelectionCriterion and implements the method select_candidates!.

Coluna.Branching.generate_children!Method
generate_children!(branching_context, branching_candidate, lhs, env, reform, node)

This method generates the children of a node described by branching_candidate.

Coluna.Branching.new_divide_outputMethod
new_divide_output(children::Union{Vector{N}, Nothing}) where {N} -> AbstractDivideOutput

where:

• N is the type of nodes generated by the branching algorithm.

If no nodes are found, the generic implementation may provide nothing.

Coluna.MustImplement.@mustimplementMacro
@mustimplement "Interface name" f(a,b,c) = nothing

Converts into a fallback for function f(a,b,c) that throws a IncompleteInterfaceError.