`Coluna.TreeSearch.AbstractExploreStrategy`

— TypeAlgorithm that chooses next node to evaluated in the tree search algorithm.

`Coluna.TreeSearch.AbstractNode`

— TypeA subspace obtained by successive divisions of the search space.

`Coluna.TreeSearch.AbstractSearchSpace`

— TypeContains the definition of the problem tackled by the tree search algorithm and how the nodes and transitions of the tree search space will be explored.

`Coluna.TreeSearch.BestDualBoundStrategy`

— TypeExplore the tree search space with a best-first strategy. The next visited node is the one with the highest local dual bound.

`Coluna.TreeSearch.DepthFirstStrategy`

— TypeExplore the tree search space with a depth-first strategy. The next visited node is the last one pushed in the stack of unexplored nodes.

`Coluna.TreeSearch.children`

— MethodEvaluate and generate children. This method has a specific implementation for Coluna.

`Coluna.TreeSearch.get_branch_description`

— MethodReturns a `String`

to display the branching constraint.

`Coluna.TreeSearch.get_conquer_output`

— MethodReturns the conquer output if the conquer was already run for this node, otherwise returns nothing

`Coluna.TreeSearch.get_parent`

— MethodReturns the parent of a node; `nothing`

if the node is the root.

`Coluna.TreeSearch.get_priority`

— MethodReturns the priority of the node depending on the explore strategy.

`Coluna.TreeSearch.isroot`

— MethodReturns `true`

is the node is root; `false`

otherwise.

`Coluna.TreeSearch.new_root`

— MethodCreates and returns the root node of a search space.

`Coluna.TreeSearch.new_space`

— MethodCreates and returns the search space of a tree search algorithm, its model, and its input.

`Coluna.TreeSearch.search_space_type`

— MethodReturns the type of search space depending on the tree-search algorithm and its parameters.

`Coluna.TreeSearch.stop`

— MethodReturns true if stopping criteria are met; false otherwise.

`Coluna.TreeSearch.tree_search`

— MethodGeneric implementation of the tree search algorithm for a given explore strategy.

`Coluna.TreeSearch.tree_search_output`

— MethodReturns the output of the tree search algorithm.

`Coluna.AlgoAPI.ColunaBase.MustImplement`

— ModuleExposes `@mustimplement`

macro to help developers identifying API definitions.

`Coluna.AlgoAPI.ColunaBase.MustImplement.IncompleteInterfaceError`

— Type`IncompleteInterfaceError <: Exception`

Exception to be thrown when an interface function is called without default implementation.

`Coluna.AlgoAPI.ColunaBase.MustImplement.@mustimplement`

— Macro`@mustimplement "Interface name" f(a,b,c) = nothing`

Converts into a fallback for function `f(a,b,c)`

that throws a `IncompleteInterfaceError`

.

`Coluna.AlgoAPI.MustImplement`

— ModuleExposes `@mustimplement`

macro to help developers identifying API definitions.

`Coluna.AlgoAPI.MustImplement.IncompleteInterfaceError`

— Type`IncompleteInterfaceError <: Exception`

Exception to be thrown when an interface function is called without default implementation.

`Coluna.AlgoAPI.MustImplement.@mustimplement`

— Macro`@mustimplement "Interface name" f(a,b,c) = nothing`

Converts into a fallback for function `f(a,b,c)`

that throws a `IncompleteInterfaceError`

.

`Coluna.ColunaBase.Bound`

— Method`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.HashTable`

— TypeThis datastructure allows us to quickly find solution that shares the same members: variables for primal solutions and constraints for dual solutions.

`Coluna.ColunaBase.Solution`

— MethodSolution 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.SolutionStatus`

— Type`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.TerminationStatus`

— Type`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.best`

— Method`best(b1, b2)`

Returns the best bound between b1 and b2.

`Coluna.ColunaBase.convert_status`

— Method```
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_record`

— Method`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.diff`

— Method```
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.gap`

— Method```
gap(pb, db)
gap(db, pb)
```

Return relative gap. Gap is non-positive if pb reached db.

`Coluna.ColunaBase.getbound`

— MethodReturn the value (as a Bound) of `solution`

`Coluna.ColunaBase.getmodel`

— MethodReturn the model of a solution.

`Coluna.ColunaBase.getstatus`

— MethodReturn the solution status of `solution`

.

`Coluna.ColunaBase.getstorage`

— MethodReturn the storage of a model.

`Coluna.ColunaBase.getvalue`

— MethodReturn the value of `solution`

.

`Coluna.ColunaBase.isbetter`

— Method`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.isinfeasible`

— Method`isinfeasible(bound)`

Return true is the primal bound or the dual bound is infeasible.

`Coluna.ColunaBase.isunbounded`

— Method`isunbounded(bound)`

Return true is the primal bound or the dual bound is unbounded.

`Coluna.ColunaBase.printbounds`

— Function`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.record`

— MethodCreates a record of information from the model or a storage unit.

`Coluna.ColunaBase.record_type`

— MethodReturns the type of record stored in a type of storage unit.

`Coluna.ColunaBase.restore_from_record!`

— MethodRestore information from the model or the storage unit that is recorded in a record.

`Coluna.ColunaBase.storage_unit`

— MethodReturns a storage unit from a given type.

`Coluna.ColunaBase.storage_unit_type`

— MethodReturns the type of storage unit that stores a type of record.

`Coluna.ColunaBase.worst`

— Method`worst(b1, b2)`

Returns the worst bound between b1 and b2.

`Coluna.ColunaBase.@exported_nestedenum`

— MacroCreate a nested enumeration and export all the items.

`Coluna.ColunaBase.@nestedenum`

— Macro`@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.AbstractBendersContext`

— TypeSupertype for the objects to which belongs the implementation of the Benders cut generation and that stores any kind of information during the execution of the Bender cut generation algorithm.

`Coluna.Benders.AbstractBendersIterationOutput`

— TypeSupertype for the custom objects that will store the output of a Benders iteration.

`Coluna.Benders.AbstractBendersOutput`

— TypeSupertype for the custom objects that will store the output of the Benders cut generation algorithm.

`Coluna.Benders.after_benders_iteration`

— MethodPlaceholder method called after each iteration of the Benders cut generation algorithm.

`Coluna.Benders.benders_iteration_output_type`

— Method`benders_iteration_output_type(context) -> Type{<:AbstractBendersIterationOutput}`

Returns the type of the custom object that will store the output of a Benders iteration.

`Coluna.Benders.benders_output_type`

— Method`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.build_primal_solution`

— MethodBuilds a primal solution to the original problem from the primal solution to the master problem and the primal solutions to the separation problems.

`Coluna.Benders.get_benders_subprobs`

— MethodReturns the separation subproblems.

`Coluna.Benders.get_dual_sol`

— MethodReturns the dual solution of the separation problem if it exists; `nothing`

otherwise.

`Coluna.Benders.get_master`

— MethodReturns the master problem.

`Coluna.Benders.get_obj_val`

— MethodReturns the objective value of the master or separation problem.

`Coluna.Benders.get_primal_sol`

— MethodReturns the primal solution of the master problem if it exists, `nothing`

otherwise.

`Coluna.Benders.get_reform`

— MethodReturns Benders reformulation.

`Coluna.Benders.insert_cuts!`

— MethodInserts the cuts into the master.

`Coluna.Benders.is_certificate`

— MethodReturns the certificate of dual infeasibility if the master is unbounded, `nothing`

otherwise.

`Coluna.Benders.is_infeasible`

— MethodReturns `true`

if the master is infeasible, `false`

otherwise.

`Coluna.Benders.is_minimization`

— MethodReturns `true`

if the objective sense is minimization, `false`

otherwise.

`Coluna.Benders.is_unbounded`

— MethodReturns `true`

if the problem is unbounded, `false`

otherwise.

`Coluna.Benders.master_is_unbounded`

— MethodReturns `true`

if the master has been proven unbounded, `false`

otherwise.

`Coluna.Benders.new_iteration_output`

— MethodReturns a new instance of the custom object that stores the output of a Benders iteration.

`Coluna.Benders.new_output`

— MethodReturns a new instance of the custom object that stores 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.run_benders_iteration!`

— MethodRuns one iteration of a Benders cut generation algorithm.

`Coluna.Benders.run_benders_loop!`

— MethodMain loop of the Benders cut generation algorithm.

`Coluna.Benders.set_of_cuts`

— MethodReturns 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.set_of_sep_sols`

— MethodReturns an empty container that will store the primal solutions to the separation problems at a given iteration of the Benders cut generation algorithm.

`Coluna.Benders.setup_reformulation!`

— MethodPrepares the reformulation before starting the Benders cut generation algorithm.

`Coluna.Benders.setup_separation_for_unbounded_master_case!`

— Method`setup_separation_for_unbounded_master_case!(context, sp, mast_primal_sol)`

Updates the separation problem to derive a cut when the master problem is unbounded.

`Coluna.Benders.stop_benders`

— MethodReturns `true`

if the Benders cut generation algorithm must stop, `false`

otherwise.

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

— TypeSearch space for tree search algorithms in Coluna.

`Coluna.Algorithm.AbstractConquerAlgorithm`

— Type`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.AbstractConquerInput`

— TypeAbstractConquerInput

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

— TypeSuper type to dispatch on file printer methods.

`Coluna.Algorithm.AbstractGlobalPrimalBoundHandler`

— TypeAbstract type for an utilarity structure that handles the incumbent primal bound.

`Coluna.Algorithm.AbstractLogPrinter`

— TypeSuper type to dispatch on log printer method.

`Coluna.Algorithm.AbstractOptimizationAlgorithm`

— Type```
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.BaBSearchSpace`

— TypeBranch-and-bound search space.

`Coluna.Algorithm.BeforeCutGenAlgo`

— TypeAlgorithm called before cut generation.

`Coluna.Algorithm.BendersContext`

— Type`BendersContext(reformulation, algo_params) -> BendersContext`

Default implementation of the Benders algorithm.

`Coluna.Algorithm.BendersCutGeneration`

— Type```
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

**About the output**

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

— TypeOutput 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.BendersMasterResult`

— TypeOutput 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.BendersOutput`

— TypeOutput 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.BendersPrinterContext`

— Type`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.BendersSeparationResult`

— TypeOutput 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.BranchingPhase`

— Type`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.ClassicBranching`

— Type```
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.ClosestToNonZeroIntegerCriterion`

— Type`Select the candidate with the smallest distance to the closest non-zero integer (often used in diving).`

`Coluna.Algorithm.ColCutGenConquer`

— Type```
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.ColGenContext`

— Type`ColGenContext(reformulation, algo_params) -> ColGenContext`

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

`Coluna.Algorithm.ColGenIterationOutput`

— TypeObject for the output of an iteration of the column generation default implementation.

`Coluna.Algorithm.ColGenMasterResult`

— TypeOutput 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.ColGenOutput`

— TypeOutput of the default implementation of the column generation algorithm.

`Coluna.Algorithm.ColGenPhase0`

— TypePhase 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.ColGenPhase1`

— TypePhase 1 sets the cost of variables to 0 except for artifical variables. The goal is to find a solution to the master LP problem that has no artificial variables.

`Coluna.Algorithm.ColGenPhase2`

— TypePhase 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.ColGenPhaseOutput`

— TypeOutput of the default implementation of a phase of the column generation algorithm.

`Coluna.Algorithm.ColGenPricingResult`

— TypeOutput 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.ColGenPrinterContext`

— Type`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.ColGenStab`

— TypeImplementation 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.ColGenStageIterator`

— TypeDefault 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.ColumnAlreadyInsertedColGenWarning`

— TypeError thrown when when a subproblem generates a column with negative (resp. positive) reduced cost in min (resp. max) problem that already exists in the master and that is already active. An active master column cannot have a negative reduced cost.

`Coluna.Algorithm.ColumnGeneration`

— Type```
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,
show_column_already_inserted_warning = true,
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.

**About the ouput**

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

— TypeStores 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.ColunaColGenPhaseIterator`

— TypeType for the default implementation of the sequence of phases.

`Coluna.Algorithm.ConquerInputFromBaB`

— TypeConquer input object created by the branch-and-bound tree search algorithm.

`Coluna.Algorithm.ConquerInputFromSb`

— TypeConquer input object created by the strong branching algorithm.

`Coluna.Algorithm.ConstrState`

— Type`ConstrState`

Used in formulation records

`Coluna.Algorithm.CustomOptimize`

— Type`CustomOptimize()`

Configuration for an optimizer that calls a custom solver to solve a custom model.

`Coluna.Algorithm.CutCallbacks`

— Type```
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.CutsSet`

— TypeStores a collection of cuts.

It contains `cuts`

a vector of `GeneratedCut`

objects.

`Coluna.Algorithm.DefaultLogPrinter`

— TypeDefault log printer.

`Coluna.Algorithm.DevNullFilePrinter`

— TypeDoes not print the branch and bound tree.

`Coluna.Algorithm.DevNullLogPrinter`

— TypeDoes not log anything.

`Coluna.Algorithm.DivideInputFromBaB`

— TypeDivide input object created by the branch-and-bound tree search algorithm.

`Coluna.Algorithm.DotFilePrinter`

— TypeFile printer to create a dot file of the branch and bound tree.

`Coluna.Algorithm.DwPresolveReform`

— TypeStores 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.FirstFoundCriterion`

— TypeSelect the branching candidates that have been generated first (sort by `local_id`

).

`Coluna.Algorithm.GeneratedColumn`

— TypeSolution 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.GeneratedCut`

— TypeSolution 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.GlobalPrimalBoundHandler`

— TypeDefault implementation of a manager of the incumbent primal bound. This implementation does not support paralellization.

`Coluna.Algorithm.IncorrectPricingDualBound`

— Type`IncorrectPricingDualBound`

Error thrown when transmitting a dual bound larger than the primal bound of the best solution to the pricing subproblem found in a run of the pricing callback.

`Coluna.Algorithm.JSONFilePrinter`

— TypeFile printer to create a JSON file of the branch and bound tree.

`Coluna.Algorithm.LeastFractionalCriterion`

— TypeSelect the least fractional branching candidates

`Coluna.Algorithm.LeavesStatus`

— TypeLeaves status

`Coluna.Algorithm.MasterBranchConstrsUnit`

— Type`MasterBranchConstrsUnit`

Unit for master branching constraints. Can be restored using MasterBranchConstrsRecord.

`Coluna.Algorithm.MasterColumnsUnit`

— Type`MasterColumnsUnit`

Unit for branching constraints of a formulation. Can be restored using a MasterColumnsRecord.

`Coluna.Algorithm.MasterCutsUnit`

— Type`MasterCutsUnit`

Unit for cutting planes of a formulation. Can be restored using a MasterCutsRecord.

`Coluna.Algorithm.MissingPricingDualBound`

— Type`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.MoiOptimize`

— Type```
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.MostFractionalCriterion`

— TypeSelect the most fractional branching candidates.

`Coluna.Algorithm.MultiplePricingDualBounds`

— Type`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.NoBranching`

— TypeDivide algorithm that does nothing. It does not generate any child.

`Coluna.Algorithm.Node`

— TypeBranch-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.OptimizationState`

— Method```
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.PresolveAlgorithm`

— TypePresolve algorithm

`Coluna.Algorithm.PresolveFormRepr`

— TypeTemporary data structure where we store a representation of the formulation that we presolve.

`Coluna.Algorithm.PresolveFormulation`

— TypeStores 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.PrintedNode`

— TypeNode that contains the node of the Coluna's tree search algorithm for which we want to print execution logs.

`Coluna.Algorithm.PrinterSearchSpace`

— TypeSearch space that contains the search space of the Coluna's tree search algorithm for which we want to print execution logs.

`Coluna.Algorithm.ReducedCostsCalculationHelper`

— TypeExtracted 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.get
*subprob*var*orig*costs - ColGen.get
*orig*coefmatrix

`Coluna.Algorithm.RestrMasterLPConquer`

— Type```
RestrMasterLPConquer(
masterlpalgo = SolveLpForm(
get_ip_primal_sol = true
)
)
```

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

`Coluna.Algorithm.RestrictedMasterHeuristic`

— TypeThe 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.RhsCalculationHelper`

— TypePrecompute 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.SepSolSet`

— TypePrimal 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.SingleVarBranchingCandidate`

— Type`SingleVarBranchingCandidate`

It is an implementation of AbstractBranchingCandidate. This is the type of branching candidates produced by the branching rule `SingleVarBranchingRule`

.

`Coluna.Algorithm.SingleVarBranchingRule`

— Type`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.SolveIpForm`

— Type```
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.SolveLpForm`

— Type```
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.StaticVarState`

— Type`StaticVarState`

Used in formulation records

`Coluna.Algorithm.StrongBranching`

— Type```
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**:

`phases`

: a vector of`Coluna.Algorithm.BranchingPhase`

`rules`

: a vector of`Coluna.Algorithm.Branching.PrioritisedBranchingRule`

`selection_criterion`

: a selection criterion to choose the initial candidates`verbose`

: if true, print the progress of the strong branching procedure`int_tol`

: tolerance to determine if a variable is integer

`Coluna.Algorithm.SubgradientCalculationHelper`

— TypePrecompute 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.SubprobPrimalSolsSet`

— TypeColumns 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.TreeSearchAlgorithm`

— Type```
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.UnexpectedEndOfColGenPhase`

— TypeThrown when the phase ended with an unexpected output. The algorithm cannot continue because theory is not verified.

`Coluna.Algorithm.UnitsUsage`

— TypeStore a set of storage unit type associated to the model. Used to indicate what storage units from what models we want to restore.

`Coluna.Algorithm.UserOptimize`

— Type```
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_coeffs`

— MethodFunction `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_contrib`

— MethodWhen 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.add_lp_dual_sol!`

— MethodSimilar to `add_ip_primal_sol!`

.

`Coluna.Algorithm.add_lp_primal_sol!`

— MethodSimilar to `add_ip_primal_sol!`

.

`Coluna.Algorithm.after_conquer!`

— MethodMethods to perform operations after the conquer algorithms. It receives the output of the conquer algorithm.

`Coluna.Algorithm.check_alg_parameters`

— Method`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_records`

— Method`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.empty_lp_dual_sols!`

— MethodSimilar to `empty_ip_primal_sols!`

.

`Coluna.Algorithm.empty_lp_primal_sols!`

— MethodSimilar to `empty_ip_primal_sols!`

.

`Coluna.Algorithm.get_best_ip_primal_sol`

— MethodReturn the best IP primal solution if it exists; `nothing`

otherwise.

`Coluna.Algorithm.get_best_lp_dual_sol`

— MethodReturn the best LP dual solution if it exists; `nothing`

otherwise.

`Coluna.Algorithm.get_best_lp_primal_sol`

— MethodReturn the best LP primal solution if it exists; `nothing`

otherwise.

`Coluna.Algorithm.get_child_algorithms`

— Method`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_conquer`

— MethodReturns the conquer algorithm.

`Coluna.Algorithm.get_divide`

— MethodReturns the divide algorithm.

`Coluna.Algorithm.get_input`

— MethodReturns the input that will be passed to an algorithm. The input can be built from information contained in a search space and a node.

`Coluna.Algorithm.get_ip_dual_bound`

— MethodReturn the best IP dual bound.

`Coluna.Algorithm.get_ip_primal_bound`

— MethodReturn the best IP primal bound.

`Coluna.Algorithm.get_ip_primal_sols`

— MethodReturn all IP primal solutions.

`Coluna.Algorithm.get_lp_dual_bound`

— MethodReturn the best LP dual bound.

`Coluna.Algorithm.get_lp_dual_sols`

— MethodReturn all LP dual solutions.

`Coluna.Algorithm.get_lp_primal_bound`

— MethodReturn the best LP primal bound.

`Coluna.Algorithm.get_lp_primal_sols`

— MethodReturn all LP primal solutions.

`Coluna.Algorithm.get_previous`

— MethodReturns the previous node explored by the tree search algorithm.

`Coluna.Algorithm.get_reformulation`

— MethodReturns the reformulation that will be passed to an algorithm.

`Coluna.Algorithm.get_units_usage`

— Method`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`

— MethodReturn the gap between the best primal and dual bounds of the integer program. Should not be used to check convergence

`Coluna.Algorithm.ip_gap_closed`

— Method`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_pruned`

— MethodReturns 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`

— MethodReturn the gap between the best primal and dual bounds of the linear program.

`Coluna.Algorithm.lp_gap_closed`

— Method`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.new_children`

— MethodCreates and returns the children of a node associated to a search space.

`Coluna.Algorithm.node_change!`

— MethodMethods 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.node_is_leaf`

— MethodPerforms operations after the divide algorithm when the current node is finally a leaf.

`Coluna.Algorithm.node_is_pruned`

— MethodMethod to perform some operations if the current node is pruned.

`Coluna.Algorithm.number_of_children`

— MethodReturns the number of children generated by the divide algorithm.

`Coluna.Algorithm.propagate_partial_sol_into_master!`

— MethodReturns the local restricted partial solution.

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

— MethodRuns 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!`

— MethodRuns 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_cutgen!`

— MethodRuns a round of cut generation. Returns `true`

if at least one cut is separated; `false`

otherwise.

`Coluna.Algorithm.run_preprocessing!`

— MethodRuns 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_dual_bound!`

— MethodSet the best IP dual bound.

`Coluna.Algorithm.set_ip_primal_bound!`

— MethodSet the best IP primal bound.

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

— MethodSet the best LP dual bound.

`Coluna.Algorithm.set_lp_dual_sol!`

— MethodSimilar to `set_ip_primal_sol!`

.

`Coluna.Algorithm.set_lp_primal_bound!`

— MethodSet the best LP primal bound.

`Coluna.Algorithm.set_lp_primal_sol!`

— MethodSimilar to `set_ip_primal_sol!`

.

`Coluna.Algorithm.set_previous!`

— MethodSets the previous node explored by the tree search algorithm.

`Coluna.Algorithm.update_ip_dual_bound!`

— MethodUpdate the dual bound of the mixed-integer program if the new one is better than the current one according to the objective sense.

`Coluna.Algorithm.update_ip_primal_bound!`

— MethodUpdate the primal bound of the mixed-integer program if the new one is better than the current one according to the objective sense.

`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.Algorithm.update_lp_dual_bound!`

— MethodUpdate the dual bound of the linear program if the new one is better than the current one according to the objective sense.

`Coluna.Algorithm.update_lp_dual_sol!`

— MethodSimilar to `update_ip_primal_sol!`

.

`Coluna.Algorithm.update_lp_primal_bound!`

— MethodUpdate the primal bound of the linear program if the new one is better than the current one according to the objective sense.

`Coluna.Algorithm.update_lp_primal_sol!`

— MethodSimilar to `update_ip_primal_sol!`

.

`Coluna.MathProg.AbstractFormulation`

— Type`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.AbstractSolution`

— TypeSupertype for solutions operated by Coluna.

`Coluna.MathProg.BendersMaster`

— TypeMaster of a formulation decomposed using Benders.

`Coluna.MathProg.BendersSp`

— MethodA Benders subproblem of a formulation decomposed using Benders.

`Coluna.MathProg.ConstrData`

— TypeInformation that defines a state of a constraint. These data might change during the optimisation procedure.

`Coluna.MathProg.Constraint`

— TypeRepresentation of a constraint in Coluna. Coefficients of variables involved in the constraints are stored in the coefficient matrix.

`Coluna.MathProg.CustomOptimizer`

— Type`CustomOptimizer <: AbstractOptimizer`

Undocumented because alpha.

`Coluna.MathProg.DualSolution`

— Method```
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.Duty`

— Type`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.DwMaster`

— TypeMaster of a formulation decomposed using Dantzig-Wolfe.

`Coluna.MathProg.DwSp`

— MethodA pricing subproblem of a formulation decomposed using Dantzig-Wolfe.

`Coluna.MathProg.FormulationBuffer`

— TypeA `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.Id`

— TypeColuna 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:

`uid`

: unique id that is global to the Coluna instance (the integer)`origin_form_uid`

: unique id of the formulation where it was generated`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.MoiConstrRecord`

— TypeStructure to hold the pointers to the MOI representation of a Coluna Constraint.

`Coluna.MathProg.MoiOptimizer`

— Type`MoiOptimizer <: AbstractOptimizer`

Wrapper that is used when the optimizer of a formulation is an `MOI.AbstractOptimizer`

, thus inheriting MOI functionalities.

`Coluna.MathProg.MoiVarRecord`

— Type`MoiVarRecord`

Structure to hold the pointers to the MOI representation of a Coluna Variable.

`Coluna.MathProg.NoOptimizer`

— Type`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.ObjValues`

— MethodA convenient structure to maintain and return incumbent bounds.

`Coluna.MathProg.Original`

— TypeFormulation provided by the user.

`Coluna.MathProg.PrimalSolution`

— Method```
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.Problem`

— Method`Problem(env)`

Constructs an empty `Problem`

.

`Coluna.MathProg.Reformulation`

— Method`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.RobustConstraintsGenerator`

— TypeConstraints generator (cut callback).

`Coluna.MathProg.UserOptimizer`

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

`Coluna.MathProg.VarConstrBuffer`

— TypeA `VarConstrBuffer{I,VC}`

stores the ids of type `I`

of the variables or constraints that will be added and removed from a formulation.

`Coluna.MathProg.VarData`

— Method`VarData`

Information that defines a state of a variable.

`Coluna.MathProg.Variable`

— Type`Variable`

Representation of a variable in Coluna.

`Base.delete!`

— Method```
delete!(formulation, varconstr)
delete!(formulation, varconstrid)
```

Delete a variable or a constraint from a formulation.

`Base.haskey`

— Method`haskey(formulation, id) -> Bool`

Returns `true`

if `formulation`

has a variable or a constraint with given `id`

.

`Coluna.ColunaBase.getstorage`

— Method`getstorage(form) -> Storage`

Returns the storage of a formulation. Read the documentation of the Storage API.

`Coluna.ColunaBase.getuid`

— Method`getuid(form) -> Int`

Returns the id of the formulation.

`Coluna.MathProg.DualBound`

— Method```
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.PrimalBound`

— Method```
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_benders_sep_sp!`

— Method`add_benders_sep_sp!(reformulation, abstractmodel)`

Add a Benders separation subproblem in the reformulation.

`Coluna.MathProg.add_dw_pricing_sp!`

— Method`add_dw_pricing_sp!(reformulation, abstractmodel)`

Add a Dantzig-Wolfe pricing subproblem in the reformulation.

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

— Method`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!`

— MethodA `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.enforce_integrality!`

— Method`enforce_integrality!(formulation)`

Set the current kind of each active & explicit variable of the formulation to its perennial kind.

`Coluna.MathProg.get_benders_sep_sps`

— Method`get_benders_sep_sps(reformulation)`

Return a `Dict{FormId, AbstractModel}`

containing all Benders separation subproblems of the reformulation.

`Coluna.MathProg.get_column_from_pool`

— Method`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_sp_lb_constrid`

— Method`get_dw_pricing_sp_lb_constrid(reformulation, spid)`

Return the `ConstrId`

of the lower bounded convexity constraint of Dantzig-Wolfe pricing subproblem with id `spid`

.

`Coluna.MathProg.get_dw_pricing_sp_ub_constrid`

— Method`get_dw_pricing_sp_ub_constrid(reformulation, spid)`

Return the `ConstrId`

of the upper bounded convexity constraint of Dantzig-Wolfe pricing subproblem with id `spid`

.

`Coluna.MathProg.get_dw_pricing_sps`

— Method`get_dw_pricing_sps(reformulation)`

Return a `Dict{FormId, AbstractModel}`

containing all Dabtzig-Wolfe pricing subproblems of the reformulation.

`Coluna.MathProg.get_optimization_target`

— MethodIf 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.get_value_in_partial_sol`

— Method```
get_value_in_partial_sol(formulation, varid)
get_value_in_partial_sol(formulation, variable)
```

Return the value of the variable in the partial solution.

`Coluna.MathProg.getbranchingpriority`

— Method```
getbranchingpriority(formulation, var)
getbranchingpriority(formulation, varid)
```

Return the branching priority of a variable

`Coluna.MathProg.getcoefmatrix`

— MethodReturns the representation of the coefficient matrix stored in the formulation manager.

`Coluna.MathProg.getconstr`

— Method`getconstr(formulation, constrid) -> Constraint`

Returns the constraint with given `constrid`

that belongs to `formulation`

.

`Coluna.MathProg.getconstrs`

— Method`getconstrs(formulation) -> Dict{ConstrId, Constraint}`

Returns all constraints in `formulation`

.

`Coluna.MathProg.getcurcost`

— Method```
getcurcost(formulation, variable)
getcurcost(formulation, varid)
```

Return the current cost of the variable in the formulation.

`Coluna.MathProg.getcurincval`

— Method```
getcurincval(formulation, varconstrid)
getcurincval(formulation, varconstr)
```

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

`Coluna.MathProg.getcurkind`

— Method```
getcurkind(formulation, variable)
getcurkind(formulation, varid)
```

Return the current kind of a variable in a formulation.

`Coluna.MathProg.getcurlb`

— Method```
getcurlb(formulation, varid)
getcurlb(formulation, var)
```

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

`Coluna.MathProg.getcurrhs`

— Method```
getcurrhs(formulation, constraint)
getcurrhs(formulation, constrid)
```

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

`Coluna.MathProg.getcursense`

— Method```
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.getcurub`

— Method```
getcurub(formulation, varid)
getcurub(formulation, var)
```

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

`Coluna.MathProg.getcustomdata`

— Method```
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.getelem`

— Method```
getelem(form, varid) -> Variable
getelem(form, constrid) -> Constraint
```

Return the element of formulation `form`

that has a given id.

`Coluna.MathProg.getmaster`

— Method`getmaster(form) -> Formulation`

Returns the master formulation of a given formulation.

`Coluna.MathProg.getmaster`

— Method`getmaster(reform) -> Formulation`

Return the formulation of the master problem.

`Coluna.MathProg.getname`

— Method```
getname(formulation, varconstr)
getname(formulation, varconstrid)
```

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

`Coluna.MathProg.getobjconst`

— MethodReturns objective constant of the formulation.

`Coluna.MathProg.getobjsense`

— MethodReturns the objective function sense of a formulation.

`Coluna.MathProg.getobjsense`

— Method`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.getoptimizer`

— MethodReturns the optimizer of a formulation at a given position.

`Coluna.MathProg.getoptimizers`

— MethodReturns the list of optimizers of a formulation.

`Coluna.MathProg.getparent`

— Method`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.getpartialsol`

— Method`getpartialsol(formulation) -> Dict{VarId,Float64}`

Returns the partial solution to the formulation.

`Coluna.MathProg.getpartialsolvalue`

— Method`getpartialsolvalue(formulation) -> Float64`

Returns the partial solution value.

`Coluna.MathProg.getperencost`

— Method```
getperencost(formulation, variable)
getperencost(formulation, varid)
```

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

`Coluna.MathProg.getperenincval`

— Method```
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.getperenkind`

— Method```
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.getperenlb`

— Method```
getperenlb(formulation, varid)
getperenlb(formulation, var)
```

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

`Coluna.MathProg.getperenrhs`

— Method```
getperenrhs(formulation, constraint)
getperenrhs(formulation, constrid)
```

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

`Coluna.MathProg.getperensense`

— Method```
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.getperenub`

— Method```
getperenub(formulation, varid)
getperenub(formulation, var)
```

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

`Coluna.MathProg.getvar`

— Method`getvar(formulation, varid) -> Variable`

Returns the variable with given `varid`

that belongs to `formulation`

.

`Coluna.MathProg.getvars`

— Method`getvars(formulation) -> Dict{VarId, Variable}`

Returns all variables in `formulation`

.

`Coluna.MathProg.in_partial_sol`

— Method```
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.iscuractive`

— Method```
iscuractive(formulation, varconstrid)
iscuractive(formulation, varconstr)
```

Return `true`

if the variable or the constraint is currently active; `false`

otherwise.

`Coluna.MathProg.isexplicit`

— Method```
isexplicit(formulation, varconstr)
isexplicit(formulation, varconstrid)
```

Return `true`

if a variable or a constraint is explicit in a formulation; `false`

otherwise.

`Coluna.MathProg.isperenactive`

— Method```
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.projection_is_possible`

— MethodReturns `true`

if we can project a solution of `form`

to the original formulation.

`Coluna.MathProg.relax_integrality!`

— Method`relax_integrality!(formulation)`

Set the current kind of each active & explicit integer or binary variable of the formulation to continuous.

`Coluna.MathProg.reset!`

— Method```
reset!(form, var)
reset!(form, varid)
reset!(form, constr)
reset!(form, constraint)
```

doc todo

`Coluna.MathProg.same_custom_data`

— Method`same_custom_data(custom_data1, custom_data2) -> Bool`

Returns `true`

if the custom data are the same, false otherwise.

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

— Method`setcurincval!(formulation, varconstrid, value::Real)`

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

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

— MethodSets objective constant of the formulation.

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

— ModuleExposes `@mustimplement`

macro to help developers identifying API definitions.

`Coluna.ColGen.MustImplement.IncompleteInterfaceError`

— Type`IncompleteInterfaceError <: Exception`

Exception to be thrown when an interface function is called without default implementation.

`Coluna.ColGen.MustImplement.@mustimplement`

— Macro`@mustimplement "Interface name" f(a,b,c) = nothing`

Converts into a fallback for function `f(a,b,c)`

that throws a `IncompleteInterfaceError`

.

`Coluna.ColGen`

— ModuleAPI and high-level implementation of the column generation algorithm in Julia.

`Coluna.ColGen.AbstractColGenContext`

— TypeSupertype 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.AbstractColGenIterationOutput`

— TypeSupertype for the objects that contains the output of a column generation iteration.

`Coluna.ColGen.AbstractColGenOutput`

— TypeSupertype for the objects that contains the output of the column generation algorithm.

`Coluna.ColGen.AbstractColGenPhase`

— TypeA phase of the column generation. Each phase is associated with a specific set up of the reformulation.

`Coluna.ColGen.AbstractColGenPhaseIterator`

— TypeAn iterator that indicates how phases follow each other.

`Coluna.ColGen.AbstractColGenPhaseOutput`

— TypeSupertype for the objects that contains the output of a column generation phase.

`Coluna.ColGen.AbstractColGenStage`

— TypeA stage of the column generation algorithm. Each stage is associated to a specific solver for each pricing subproblem.

`Coluna.ColGen.AbstractColGenStageIterator`

— TypeAn iterator that indicates how stages follow each other.

`Coluna.ColGen.AbstractPricingStrategy`

— TypeA 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_iteration`

— MethodPlaceholder 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_iteration`

— MethodPlaceholder 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.check_misprice`

— MethodReturns `true`

if the stabilized dual solution leads to a misprice, `false`

otherwise.

`Coluna.ColGen.check_primal_ip_feasibility!`

— MethodReturns a primal solution expressed in the original problem variables if the current master LP solution is integer feasible; `nothing`

otherwise.

`Coluna.ColGen.colgen_iteration_output_type`

— Method`colgen_iteration_output_type(ctx) -> Type{<:AbstractColGenIterationOutput}`

Returns the type of the column generation iteration output associated to the context.

`Coluna.ColGen.colgen_output_type`

— Method`colgen_output_type(ctx) -> Type{<:AbstractColGenOutput}`

Returns the type of the column generation output associated to the context.

`Coluna.ColGen.colgen_phase_output_type`

— Method`colgen_phase_outputype(ctx) -> Type{<:AbstractColGenPhaseOutput}`

Returns the type of the column generation phase output associated to the context.

`Coluna.ColGen.compute_dual_bound`

— Method`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.compute_sp_init_db`

— MethodReturns an initial dual bound for a pricing subproblem. Default value should be +/- infinite depending on the optimization sense.

`Coluna.ColGen.compute_sp_init_pb`

— MethodReturns an initial primal bound for a pricing subproblem. Default value should be +/- infinite depending on the optimization sense.

`Coluna.ColGen.decrease_stage`

— MethodReturns 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_bound`

— MethodReturns 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_dual_sol`

— MethodReturns dual solution to the master optimization problem.

`Coluna.ColGen.get_master`

— MethodReturns master formulation.

`Coluna.ColGen.get_master_dual_sol`

— MethodReturns the dual master LP solution found at the last iteration of the column generation algorithm.

`Coluna.ColGen.get_master_ip_primal_sol`

— MethodReturns the incumbent primal master IP solution at the end of an iteration or a phase.

`Coluna.ColGen.get_master_lp_primal_bound`

— MethodReturns the master LP solution value at the last iteration of the column generation algorithm.

`Coluna.ColGen.get_master_lp_primal_sol`

— MethodReturns the primal master LP solution found at the last iteration of the column generation algorithm.

`Coluna.ColGen.get_nb_new_cols`

— MethodReturns the number of new columns inserted into the master at the end of an iteration.

`Coluna.ColGen.get_obj_val`

— MethodReturns the optimal objective value of the master LP problem." See `optimize_master_lp_problem!`

.

`Coluna.ColGen.get_output_str`

— MethodReturns a string with a short information about the stabilization.

`Coluna.ColGen.get_pricing_strategy`

— Method`get_pricing_strategy(ctx, phase) -> AbstractPricingStrategy`

Returns the pricing strategy object.

`Coluna.ColGen.get_pricing_subprob_optimizer`

— MethodReturns the optimizer for the pricing subproblem associated to the given stage.

`Coluna.ColGen.get_pricing_subprobs`

— Method`get_pricing_subprobs(ctx) -> Vector{Tuple{SuproblemId, SpFormulation}}`

Returns subproblem formulations.

`Coluna.ColGen.get_primal_bound`

— MethodReturns 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.get_primal_sol`

— MethodReturns primal solution to the master LP problem.

`Coluna.ColGen.get_primal_sols`

— MethodArray of primal solutions to the pricing subproblem

`Coluna.ColGen.get_reform`

— MethodReturns Dantzig-Wolfe reformulation.

`Coluna.ColGen.get_stab_dual_sol`

— MethodReturns the dual solution used for the pricing in the current column generation iteration (stabilized dual solution).

`Coluna.ColGen.get_subprob_var_coef_matrix`

— MethodReturns the coefficient matrix `A`

of subproblem variables in the master to compute reduced cost `̄c = c - transpose(A) * π`

.

`Coluna.ColGen.get_subprob_var_orig_costs`

— MethodReturns the original cost `c`

of subproblems variables. to compute reduced cost `̄c = c - transpose(A) * π`

.

`Coluna.ColGen.initial_phase`

— MethodReturns the phase with which the column generation algorithm must start.

`Coluna.ColGen.initial_stage`

— MethodReturns the stage at which the column generation algorithm must start.

`Coluna.ColGen.insert_columns!`

— MethodInserts 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.is_better_dual_bound`

— MethodReturns `true`

if `new_dual_bound`

is better than `dual_bound`

; `false`

otherwise.

`Coluna.ColGen.is_better_primal_sol`

— MethodReturns `true`

if the new master IP primal solution is better than the current; `false`

otherwise.

`Coluna.ColGen.is_exact_stage`

— MethodReturns `true`

if the stage uses an exact solver for the pricing subproblem; `false`

otherwise.

`Coluna.ColGen.is_infeasible`

— MethodReturns true if a master or pricing problem result is infeasible; false otherwise.

`Coluna.ColGen.is_minimization`

— MethodReturns `true`

if the objective sense is minimization; `false`

otherwise.

`Coluna.ColGen.is_unbounded`

— MethodReturns true if a master or pricing problem result is unbounded; false otherwise.

`Coluna.ColGen.new_iteration_output`

— Method`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_output`

— Method`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_iterator`

— MethodReturns a new phase iterator.

`Coluna.ColGen.new_phase_output`

— Method`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.new_stage_iterator`

— MethodReturns a new stage iterator.

`Coluna.ColGen.next_phase`

— MethodReturns the next phase of the column generation algorithm. Returns `nothing`

if the algorithm must stop.

`Coluna.ColGen.next_stage`

— MethodReturns the next stage that column generation must use.

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

— Method```
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!`

— MethodPushes 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_columns`

— MethodReturns 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.setup_context!`

— MethodSetup the context for the given phase.

`Coluna.ColGen.setup_reformulation!`

— MethodSetup the reformulation for the given phase.

`Coluna.ColGen.setup_stabilization!`

— MethodReturns an instance of a data structure that contain information about the stabilization used in the column generation algorithm.

`Coluna.ColGen.stage_id`

— MethodReturns the id of the stage.

`Coluna.ColGen.stop_colgen`

— MethodReturns `true`

when the column generation algorithm must stop; `false`

otherwise.

`Coluna.ColGen.stop_colgen_phase`

— MethodReturns `true`

if the column generation phase must stop.

`Coluna.ColGen.update_inc_primal_sol!`

— MethodUpdates the current master IP primal solution.

`Coluna.ColGen.update_master_constrs_dual_vals!`

— MethodUpdates dual value of the master constraints. Dual values of the constraints can be used when the pricing solver supports non-robust cuts.

`Coluna.ColGen.update_reduced_costs!`

— MethodMethod that you can implement if you want to store the reduced cost of subproblem variables in the context.

`Coluna.ColGen.update_sp_vars_red_costs!`

— MethodUpdates reduced costs of variables of a given subproblem.

`Coluna.ColGen.update_stabilization_after_iter!`

— MethodUpdates 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_misprice!`

— MethodUpdates stabilization after a misprice. Argument `mast_dual_sol`

is the dual solution to the master problem.

`Coluna.ColGen.update_stabilization_after_pricing_optim!`

— MethodUpdates 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.AbstractAlgorithm`

— TypeSupertype 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.AbstractDivideAlgorithm`

— TypeThis algorithm type is used by the tree search algorithm to generate nodes.

`Coluna.AlgoAPI.change_model_state`

— MethodReturns `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.run!`

— Method`run!(algo::AbstractAlgorithm, env, model, input)`

Default method to call an algorithm.

`Coluna.AlgoAPI.ColunaBase.Bound`

— Method`Bound(min, primal)`

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

`Coluna.AlgoAPI.ColunaBase.HashTable`

— TypeThis datastructure allows us to quickly find solution that shares the same members: variables for primal solutions and constraints for dual solutions.

`Coluna.AlgoAPI.ColunaBase.Solution`

— MethodSolution 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.SolutionStatus`

— Type`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.TerminationStatus`

— Type`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.best`

— Method`best(b1, b2)`

Returns the best bound between b1 and b2.

`Coluna.AlgoAPI.ColunaBase.convert_status`

— Method```
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.create_record`

— Method`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.AlgoAPI.ColunaBase.diff`

— Method```
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.gap`

— Method```
gap(pb, db)
gap(db, pb)
```

Return relative gap. Gap is non-positive if pb reached db.

`Coluna.AlgoAPI.ColunaBase.getbound`

— MethodReturn the value (as a Bound) of `solution`

`Coluna.AlgoAPI.ColunaBase.getmodel`

— MethodReturn the model of a solution.

`Coluna.AlgoAPI.ColunaBase.getstatus`

— MethodReturn the solution status of `solution`

.

`Coluna.AlgoAPI.ColunaBase.getstorage`

— MethodReturn the storage of a model.

`Coluna.AlgoAPI.ColunaBase.getvalue`

— MethodReturn the value of `solution`

.

`Coluna.AlgoAPI.ColunaBase.isbetter`

— Method`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.isinfeasible`

— Method`isinfeasible(bound)`

Return true is the primal bound or the dual bound is infeasible.

`Coluna.AlgoAPI.ColunaBase.isunbounded`

— Method`isunbounded(bound)`

Return true is the primal bound or the dual bound is unbounded.

`Coluna.AlgoAPI.ColunaBase.printbounds`

— Function`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.record`

— MethodCreates a record of information from the model or a storage unit.

`Coluna.AlgoAPI.ColunaBase.record_type`

— MethodReturns the type of record stored in a type of storage unit.

`Coluna.AlgoAPI.ColunaBase.restore_from_record!`

— MethodRestore information from the model or the storage unit that is recorded in a record.

`Coluna.AlgoAPI.ColunaBase.storage_unit`

— MethodReturns a storage unit from a given type.

`Coluna.AlgoAPI.ColunaBase.storage_unit_type`

— MethodReturns the type of storage unit that stores a type of record.

`Coluna.AlgoAPI.ColunaBase.worst`

— Method`worst(b1, b2)`

Returns the worst bound between b1 and b2.

`Coluna.AlgoAPI.ColunaBase.@exported_nestedenum`

— MacroCreate a nested enumeration and export all the items.

`Coluna.AlgoAPI.ColunaBase.@nestedenum`

— Macro`@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.Params`

— Type```
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.check_annotations`

— MethodMake sure that all variables and constraints of the original formulation are annotated. Otherwise, it returns an error.

`Coluna.optimize!`

— MethodFallback if no solver provided by the user.

`Coluna.optimize!`

— MethodStarting point of the solver.

`Coluna.reformulate!`

— MethodReformulate the original formulation of prob according to the annotations. The environment maintains formulation ids.

`Coluna.ColunaBase.MustImplement`

— ModuleExposes `@mustimplement`

macro to help developers identifying API definitions.

`Coluna.ColunaBase.MustImplement.IncompleteInterfaceError`

— Type`IncompleteInterfaceError <: Exception`

Exception to be thrown when an interface function is called without default implementation.

`Coluna.ColunaBase.MustImplement.@mustimplement`

— Macro`@mustimplement "Interface name" f(a,b,c) = nothing`

Converts into a fallback for function `f(a,b,c)`

that throws a `IncompleteInterfaceError`

.

`Coluna.Benders.MustImplement`

— ModuleExposes `@mustimplement`

macro to help developers identifying API definitions.

`Coluna.Benders.MustImplement.IncompleteInterfaceError`

— Type`IncompleteInterfaceError <: Exception`

Exception to be thrown when an interface function is called without default implementation.

`Coluna.Benders.MustImplement.@mustimplement`

— Macro`@mustimplement "Interface name" f(a,b,c) = nothing`

Converts into a fallback for function `f(a,b,c)`

that throws a `IncompleteInterfaceError`

.

`Coluna.Branching.AbstractBranchingCandidate`

— TypeA branching candidate is a data structure that contain all information needed to generate children of a node.

`Coluna.Branching.AbstractBranchingRule`

— TypeSupertype of branching rules.

`Coluna.Branching.AbstractBranchingScore`

— TypeSupertype of branching scores.

`Coluna.Branching.AbstractDivideContext`

— TypeSupertype for divide algorithm contexts.

`Coluna.Branching.AbstractDivideInput`

— TypeInput of a divide algorithm used by the tree search algorithm. Contains the parent node in the search tree for which children should be generated.

`Coluna.Branching.AbstractDivideOutput`

— TypeOutput of a divide algorithm used by the tree search algorithm. Should contain the vector of generated nodes.

`Coluna.Branching.AbstractSelectionCriterion`

— TypeSupertype 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.AbstractStrongBrContext`

— TypeSupertype for the strong branching contexts.

`Coluna.Branching.AbstractStrongBrPhaseContext`

— TypeSupertype for the branching phase contexts.

`Coluna.Branching.BranchingRuleInput`

— TypeInput of a branching rule (branching separation algorithm) Contains current solution, max number of candidates and local candidate id.

`Coluna.Branching.BranchingRuleOutput`

— TypeOutput of a branching rule (branching separation algorithm) It contains the branching candidates generated and the updated local id value

`Coluna.Branching.PrioritisedBranchingRule`

— Type`PrioritisedBranchingRule`

A branching rule with root and non-root priorities.

`Coluna.Branching.advanced_select!`

— MethodAdvanced candidates selection that selects candidates by evaluating their children.

`Coluna.Branching.apply_branching_rule`

— MethodReturns all candidates that satisfy a given branching rule.

`Coluna.Branching.branching_context_type`

— MethodReturns the type of context required by the algorithm parameters.

`Coluna.Branching.compute_score`

— MethodReturns the score of a candidate.

`Coluna.Branching.eval_candidate_inner!`

— MethodEvaluates a candidate.

`Coluna.Branching.eval_child_of_candidate!`

— MethodEvaluate children of a candidate.

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

— MethodList of storage units to restore before evaluating the node.

`Coluna.Branching.get_conquer`

— MethodReturns the conquer algorithm used to evaluate the candidate's children at a given strong branching phase.

`Coluna.Branching.get_int_tol`

— MethodReturns integer tolerance.

`Coluna.Branching.get_lhs`

— MethodReturns the left-hand side of the candidate.

`Coluna.Branching.get_local_id`

— MethodReturns the generation id of the candidiate.

`Coluna.Branching.get_max_nb_candidates`

— MethodReturns the maximum number of candidates kept at the end of a given strong branching phase.

`Coluna.Branching.get_phases`

— MethodReturns all phases context of the strong branching algorithm.

`Coluna.Branching.get_rules`

— MethodReturns branching rules.

`Coluna.Branching.get_score`

— MethodReturns the type of score used to rank the candidates at a given strong branching phase.

`Coluna.Branching.get_selection_criterion`

— MethodReturns the selection criterion.

`Coluna.Branching.get_selection_nb_candidates`

— MethodReturns the number of candidates that the candidates selection step must return.

`Coluna.Branching.get_units_to_restore_for_conquer`

— MethodReturns the storage units that must be restored by the conquer algorithm called by the strong branching phase.

`Coluna.Branching.getdescription`

— MethodReturns a string which serves to print the branching rule in the logs.

`Coluna.Branching.new_context`

— MethodCreates a context.

`Coluna.Branching.new_divide_output`

— Method`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.Branching.new_phase_context`

— MethodCreates a context for the branching phase.

`Coluna.Branching.perform_branching_phase_inner!`

— MethodPerforms a branching phase.

`Coluna.Branching.select!`

— MethodCandidates selection for branching algorithms.

`Coluna.Branching.select_candidates!`

— MethodSort branching candidates according to the selection criterion and remove excess ones.

`Coluna.MustImplement`

— ModuleExposes `@mustimplement`

macro to help developers identifying API definitions.

`Coluna.MustImplement.IncompleteInterfaceError`

— Type`IncompleteInterfaceError <: Exception`

Exception to be thrown when an interface function is called without default implementation.

`Coluna.MustImplement.@mustimplement`

— Macro`@mustimplement "Interface name" f(a,b,c) = nothing`

Converts into a fallback for function `f(a,b,c)`

that throws a `IncompleteInterfaceError`

.