Built-in Algorithms

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

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

The three main elements of the algorithm are:

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

Parameters:

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

Options:

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

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

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

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

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.

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

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.

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

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

CutCallbacks(
    call_robust_facultative = true,
    call_robust_essential = true,
    tol::Float64 = 1e-6
)

Runs the cut user callbacks attached to a formulation.

Parameters:

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

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

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

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

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

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

Parameters:

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

Options:

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

Undocumented parameters are in alpha version.

About the ouput

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

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

Here are their meanings :

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

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

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

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

Parameters:

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

Undocumented parameters are alpha.

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

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

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

CustomOptimize()

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