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

A subspace obtained by successive divisions of the search space.

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

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

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

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

Returns a String to display the branching constraint.

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

Returns the parent of a node; nothing if the node is the root.

Returns the priority of the node depending on the explore strategy.

Returns true is the node is root; false otherwise.

Creates and returns the root node of a search space.

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

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

Returns true if stopping criteria are met; false otherwise.

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

Returns the output of the tree search algorithm.

Exposes @mustimplement macro to help developers identifying API definitions.

IncompleteInterfaceError <: Exception

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

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

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

Exposes @mustimplement macro to help developers identifying API definitions.

IncompleteInterfaceError <: Exception

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

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

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

Bound(min, primal)

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

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

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

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

Create a solution to the model. Other arguments are:

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

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

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.

best(b1, b2)

Returns the best bound between b1 and b2.

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.

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.

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.

gap(pb, db)
gap(db, pb)

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

Return the value (as a Bound) of solution

Return the model of a solution.

Return the solution status of solution.

Return the storage of a model.

Return the value of solution.

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.

isinfeasible(bound)

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

isunbounded(bound)

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

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.

Creates a record of information from the model or a storage unit.

Returns the type of record stored in a type of storage unit.

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

Returns a storage unit from a given type.

Returns the type of storage unit that stores a type of record.

worst(b1, b2)

Returns the worst bound between b1 and b2.

Create a nested enumeration and export all the items.

@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

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

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

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

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

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

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

benders_output_type(context) -> Type{<:AbstractBendersOutput}

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

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

Returns the separation subproblems.

Returns the dual solution of the separation problem if it exists; nothing otherwise.

Returns the master problem.

Returns the objective value of the master or separation problem.

Returns the primal solution of the master problem if it exists, nothing otherwise.

Returns Benders reformulation.

Inserts the cuts into the master.

Returns the certificate of dual infeasibility if the master is unbounded, nothing otherwise.

Returns true if the master is infeasible, false otherwise.

Returns true if the objective sense is minimization, false otherwise.

Returns true if the problem is unbounded, false otherwise.

Returns true if the master has been proven unbounded, false otherwise.

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

Returns a new instance of the custom object that stores the output of the Benders cut generation algorithm.

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}

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}

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.

Runs one iteration of a Benders cut generation algorithm.

Main loop of the Benders cut generation algorithm.

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

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

Prepares the reformulation before starting the Benders cut generation algorithm.

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.

Returns true if the Benders cut generation algorithm must stop, false otherwise.

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.

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.

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.

Search space for tree search algorithms in Coluna.

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

AbstractConquerInput

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

Super type to dispatch on file printer methods.

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

Super type to dispatch on log printer method.

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.

Branch-and-bound search space.

Algorithm called before cut generation.

BendersContext(reformulation, algo_params) -> BendersContext

Default implementation of the Benders algorithm.

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

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

It contains:

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

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

It contains:

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

Output of the default implementation of the Benders algorithm.

It contains:

• infeasible: the original problem is infeasible
• time_limit_reached: the time limit was reached
• mlp: the final bound obtained with the Benders cut algorithm
• ip_primal_sol: the best primal solution to the original problem found by the Benders cut algorithm

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.

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

It contains:

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

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.

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.

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

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

ColGenContext(reformulation, algo_params) -> ColGenContext

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

Object for the output of an iteration of the column generation default implementation.

Output of the ColGen.optimize_master_lp_problem! method.

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

Output of the default implementation of the column generation algorithm.

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

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

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

Output of the default implementation of a phase of the column generation algorithm.

Output of the default implementation of ColGen.optimize_pricing_problem!.

It contains:

• result: the output of the SolveIpForm algorithm called to optimize the pricing subproblem
• columns: a vector of GeneratedColumn objects obtained by processing of the output of pricing subproblem optimization, it stores the reduced cost of each column
• best_red_cost: the best reduced cost of the columns

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.

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

TODO: docstring

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

Default implementation of the column generation stages works as follows.

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

The column generation algorithm will run the following stages:

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

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

Error 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(
    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

Stores a collection of columns.

It contains:

• columns: a vector of GeneratedColumn objects by all pricing subproblems that will be inserted into the master
• subprob_primal_solutions: an object that stores the best columns generated by each pricing subproblem at this iteration.

Type for the default implementation of the sequence of phases.

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

Conquer input object created by the strong branching algorithm.

ConstrState

Used in formulation records

CustomOptimize()

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

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.

Stores a collection of cuts.

It contains cuts a vector of GeneratedCut objects.

Default log printer.

Does not print the branch and bound tree.

Does not log anything.

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

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

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

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

Select the branching candidates that have been generated first (sort by local_id).

Solution to a pricing subproblem after a given optimization.

It contains:

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

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

It contains:

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

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

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.

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

Select the least fractional branching candidates

Leaves status

MasterBranchConstrsUnit

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

MasterColumnsUnit

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

MasterCutsUnit

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

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.

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

Select the most fractional branching candidates.

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.

Divide algorithm that does nothing. It does not generate any child.

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

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.

Presolve algorithm

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

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

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

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

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

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

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

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

Calculation is c - transpose(A) * master_lp_dual_solution.

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

• ColGen.getsubprobvarorigcosts
• ColGen.getorigcoefmatrix

RestrMasterLPConquer(
    masterlpalgo = SolveLpForm(
        get_ip_primal_sol = true
    )
)

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

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

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

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

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

It contains sols a vector of primal solutions.

SingleVarBranchingCandidate

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

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

StaticVarState

Used in formulation records

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

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

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

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

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

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

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

It contains:

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

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

Coluna.Algorithm.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.

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

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

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

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

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

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)

Similar to add_ip_primal_sol!.

Similar to add_ip_primal_sol!.

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

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.

create_records(reformulation) -> Records

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

empty_ip_primal_sols!(optstate)

Remove all IP primal solutions from optstate.

Similar methods :

empty_lp_primal_sols!(optstate)
empty_lp_dual_sols!(optstate)

Similar to empty_ip_primal_sols!.

Similar to empty_ip_primal_sols!.

Return the best IP primal solution if it exists; nothing otherwise.

Return the best LP dual solution if it exists; nothing otherwise.

Return the best LP primal solution if it exists; nothing otherwise.

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.

Returns the conquer algorithm.

Returns the divide algorithm.

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

Return the best IP dual bound.

Return the best IP primal bound.

Return all IP primal solutions.

Return the best LP dual bound.

Return all LP dual solutions.

Return the best LP primal bound.

Return all LP primal solutions.

Returns the previous node explored by the tree search algorithm.

Returns the reformulation that will be passed to an algorithm.

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.

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

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.

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

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

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.

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

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

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

Method to perform some operations if the current node is pruned.

Returns the number of children generated by the divide algorithm.

Returns the local restricted partial solution.

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.

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

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

Runs a round of cut generation. Returns true if at least one cut is separated; false otherwise.

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

Set the best IP dual bound.

Set the best IP primal bound.

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)

Set the best LP dual bound.

Similar to set_ip_primal_sol!.

Set the best LP primal bound.

Similar to set_ip_primal_sol!.

Sets the previous node explored by the tree search algorithm.

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

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

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)

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

Similar to update_ip_primal_sol!.

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

Similar to update_ip_primal_sol!.

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.

Supertype for solutions operated by Coluna.

Master of a formulation decomposed using Benders.

A Benders subproblem of a formulation decomposed using Benders.

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

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

CustomOptimizer <: AbstractOptimizer

Undocumented because alpha.

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.

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

Master of a formulation decomposed using Dantzig-Wolfe.

A pricing subproblem of a formulation decomposed using Dantzig-Wolfe.

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

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

Coluna identifier of a Variable or a Constraint.

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

It is composed by the following ids:

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

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

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

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

MoiOptimizer <: AbstractOptimizer

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

MoiVarRecord

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

NoOptimizer <: AbstractOptimizer

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

A convenient structure to maintain and return incumbent bounds.

Formulation provided by the user.

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.

Problem(env)

Constructs an empty Problem.

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.

Constraints generator (cut callback).

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.

A VarConstrBuffer{I,VC} stores the ids of type I of the variables or constraints that will be added and removed from a formulation.

VarData

Information that defines a state of a variable.

Variable

Representation of a variable in Coluna.

delete!(formulation, varconstr)
delete!(formulation, varconstrid)

Delete a variable or a constraint from a formulation.

haskey(formulation, id) -> Bool

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

getstorage(form) -> Storage

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

getuid(form) -> Int

Returns the id of the formulation.

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.

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.

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.

add_benders_sep_sp!(reformulation, abstractmodel)

Add a Benders separation subproblem in the reformulation.

add_dw_pricing_sp!(reformulation, abstractmodel)

Add a Dantzig-Wolfe pricing subproblem in the reformulation.

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.

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.

A Formulation stores a mixed-integer linear program.

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

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

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.

enforce_integrality!(formulation)

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

get_benders_sep_sps(reformulation)

Return a Dict{FormId, AbstractModel} containing all Benders separation subproblems of the reformulation.

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.

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.

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.

get_dw_pricing_sps(reformulation)

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

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

get_value_in_partial_sol(formulation, varid)
get_value_in_partial_sol(formulation, variable)

Return the value of the variable in the partial solution.

getbranchingpriority(formulation, var)
getbranchingpriority(formulation, varid)

Return the branching priority of a variable

Returns the representation of the coefficient matrix stored in the formulation manager.

getconstr(formulation, constrid) -> Constraint

Returns the constraint with given constrid that belongs to formulation.

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

Returns all constraints in formulation.

getcurcost(formulation, variable)
getcurcost(formulation, varid)

Return the current cost of the variable in the formulation.

getcurincval(formulation, varconstrid)
getcurincval(formulation, varconstr)

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

getcurkind(formulation, variable)
getcurkind(formulation, varid)

Return the current kind of a variable in a formulation.

getcurlb(formulation, varid)
getcurlb(formulation, var)

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

getcurrhs(formulation, constraint)
getcurrhs(formulation, constrid)

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

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.

getcurub(formulation, varid)
getcurub(formulation, var)

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

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.

getelem(form, varid) -> Variable
getelem(form, constrid) -> Constraint

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

getmaster(form) -> Formulation

Returns the master formulation of a given formulation.

getmaster(reform) -> Formulation

Return the formulation of the master problem.

getname(formulation, varconstr)
getname(formulation, varconstrid)

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

Returns objective constant of the formulation.

Returns the objective function sense of a formulation.

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.

Returns the optimizer of a formulation at a given position.

Returns the list of optimizers of a formulation.

getparent(form) -> AbstractFormulation

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

• the master for a subproblem
• the reformulation for the master

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

Returns the partial solution to the formulation.

getpartialsolvalue(formulation) -> Float64

Returns the partial solution value.

getperencost(formulation, variable)
getperencost(formulation, varid)

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

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.

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.

getperenlb(formulation, varid)
getperenlb(formulation, var)

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

getperenrhs(formulation, constraint)
getperenrhs(formulation, constrid)

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

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.

getperenub(formulation, varid)
getperenub(formulation, var)

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

getvar(formulation, varid) -> Variable

Returns the variable with given varid that belongs to formulation.

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

Returns all variables in formulation.

in_partial_sol(form, varid)
in_partial_sol(form, variable)

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

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.

iscuractive(formulation, varconstrid)
iscuractive(formulation, varconstr)

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

isexplicit(formulation, varconstr)
isexplicit(formulation, varconstrid)

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

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.

Returns true if we can project a solution of form to the original formulation.

relax_integrality!(formulation)

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

reset!(form, var)
reset!(form, varid)
reset!(form, constr)
reset!(form, constraint)

doc todo

same_custom_data(custom_data1, custom_data2) -> Bool

Returns trueif the custom data are the same, false otherwise.

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

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.

setcurincval!(formulation, varconstrid, value::Real)

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

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

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.

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.

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.

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.

Sets objective constant of the formulation.

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.

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.

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.

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.

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.

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.

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

Exposes @mustimplement macro to help developers identifying API definitions.

IncompleteInterfaceError <: Exception

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

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

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

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

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

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

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

Supertype for the objects that contains the output of the column generation algorithm.

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

An iterator that indicates how phases follow each other.

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

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

An iterator that indicates how stages follow each other.

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

Basically, this object is used like this:

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

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

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

Returns true if the stabilized dual solution leads to a misprice, false otherwise.

Returns a primal solution expressed in the original problem variables if the current master LP solution is integer feasible; nothing otherwise.

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

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

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

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

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

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

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.

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

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

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

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

Returns dual solution to the master optimization problem.

Returns master formulation.

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

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

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

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

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

Returns the optimal objective value of the master LP problem." See optimize_master_lp_problem!.

Returns a string with a short information about the stabilization.

get_pricing_strategy(ctx, phase) -> AbstractPricingStrategy

Returns the pricing strategy object.

Returns the optimizer for the pricing subproblem associated to the given stage.

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

Returns subproblem formulations.

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

Returns primal solution to the master LP problem.

Array of primal solutions to the pricing subproblem

Returns Dantzig-Wolfe reformulation.

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

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

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

Returns the phase with which the column generation algorithm must start.

Returns the stage at which the column generation algorithm must start.

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

Returns true if new_dual_bound is better than dual_bound; false otherwise.

Returns true if the new master IP primal solution is better than the current; false otherwise.

Returns true if the stage uses an exact solver for the pricing subproblem; false otherwise.

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

Returns true if the objective sense is minimization; false otherwise.

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

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

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.

Returns a new phase iterator.

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

Returns a new stage iterator.

Returns the next phase of the column generation algorithm. Returns nothing if the algorithm must stop.

Returns the next stage that column generation must use.

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.

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

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.

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

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.

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

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.

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

Setup the context for the given phase.

Setup the reformulation for the given phase.

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

Returns the id of the stage.

Returns true when the column generation algorithm must stop; false otherwise.

Returns true if the column generation phase must stop.

Updates the current master IP primal solution.

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

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

Updates reduced costs of variables of a given subproblem.

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

• stab is the stabilization data structure
• ctx is the column generation context
• master is the master problem
• generated_columns is the set of generated columns
• mast_dual_sol is the dual solution to the master problem

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.

Updates stabilization after a misprice. Argument mast_dual_sol is the dual solution to the master problem.

Updates stabilization after pricing optimization where:

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

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

For instance:

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

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

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

run!(algo::AbstractAlgorithm, env, model, input)

Default method to call an algorithm.

Bound(min, primal)

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

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

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

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

Create a solution to the model. Other arguments are:

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

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

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.

best(b1, b2)

Returns the best bound between b1 and b2.

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.

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.

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.

gap(pb, db)
gap(db, pb)

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

Return the value (as a Bound) of solution

Return the model of a solution.

Return the solution status of solution.

Return the storage of a model.

Return the value of solution.

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.

isinfeasible(bound)

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

isunbounded(bound)

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

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.

Creates a record of information from the model or a storage unit.

Returns the type of record stored in a type of storage unit.

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

Returns a storage unit from a given type.

Returns the type of storage unit that stores a type of record.

worst(b1, b2)

Returns the worst bound between b1 and b2.

Create a nested enumeration and export all the items.

@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(
    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

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

Fallback if no solver provided by the user.

Starting point of the solver.

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

Exposes @mustimplement macro to help developers identifying API definitions.

IncompleteInterfaceError <: Exception

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

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

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

Exposes @mustimplement macro to help developers identifying API definitions.

IncompleteInterfaceError <: Exception

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

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

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

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

Supertype of branching rules.

Supertype of branching scores.

Supertype for divide algorithm contexts.

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

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

Supertype of selection criteria of branching candidates.

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

Supertype for the strong branching contexts.

Supertype for the branching phase contexts.

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

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

PrioritisedBranchingRule

A branching rule with root and non-root priorities.

Advanced candidates selection that selects candidates by evaluating their children.

Returns all candidates that satisfy a given branching rule.

Returns the type of context required by the algorithm parameters.

Returns the score of a candidate.

Evaluates a candidate.

Evaluate children of a candidate.

generate_children!(branching_context, branching_candidate, lhs, env, reform, node)

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

List of storage units to restore before evaluating the node.

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

Returns integer tolerance.

Returns the left-hand side of the candidate.

Returns the generation id of the candidiate.

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

Returns all phases context of the strong branching algorithm.

Returns branching rules.

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

Returns the selection criterion.

Returns the number of candidates that the candidates selection step must return.

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

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

Creates a context.

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.

Creates a context for the branching phase.

Performs a branching phase.

Candidates selection for branching algorithms.

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

Exposes @mustimplement macro to help developers identifying API definitions.

IncompleteInterfaceError <: Exception

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

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

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