GitHub

Column generation

Coluna provides an interface and generic functions to implement a multi-stage column generation algorithm together with a default implementation of this algorithm.

In this section, we are first going to present the generic functions, the implementation with some theory backgrounds and then give the references of the interface.

You can find the generic functions and the interface in the ColGen submodule and the default implementation in the Algorithm submodule at src/Algorithm/colgen.

Context

The ColGen submodule provides an interface and generic functions to implement a column generation algorithm. The implementation depends on an object called context.

Coluna.ColGen.AbstractColGenContext — Type

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.

source

Coluna provides two types of context:

Coluna.Algorithm.ColGenContext — Type
ColGenContext(reformulation, algo_params) -> ColGenContext

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

source
Coluna.Algorithm.ColGenPrinterContext — Type
ColGenPrinterContext(reformulation, algo_params) -> ColGenPrinterContext

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

source

Generic functions

Generic functions are the core of the column generation algorithm. There are three generic functions:

Coluna.ColGen.run! — Function
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.

source

See the main loop section for more details.

Coluna.ColGen.run_colgen_phase! — Function
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.

source

See the phase loop section for more details.

Coluna.ColGen.run_colgen_iteration! — Function
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
source

See the column generation iteration section for more details.

They are independent of any other submodule of Coluna. You can use them to implement your own column generation algorithm.

Reformulation

The default implementation works with a reformulated problem contained in MathProg.Reformulation where master and subproblems are MathProg.Formulation objects.

The master has the following form:

\[\begin{aligned} \min \quad& \sum_{k \in K} c^k \lambda^k+\bar{c} y & \\ \text{s.t.} \quad& \sum_{k \in K} A^k \lambda^k+\bar{A} y \geq a & (1)\\ & l_k \leq \mathbf{1} \lambda^k \leq u_k & (2) \\ & \bar{l} \leq y \leq \bar{u} & (3) \end{aligned}\]

where $\lambda$ are the master columns, $y$ are the pure master variables, constraints (1) are the linking constraints, constraints (2) are the convexity constraints that depend on $l_k$ and $u_k$ (e.g. the lower and upper multiplicity of the subproblem $k$ respectively), and constraints (3) are the bounds on the pure master variables.

The subproblems have the following form:

\[\begin{aligned} \min \quad& cx + 0z \\ \text{s.t.} \quad& Bx \geq b \\ & 1 \leq z \leq 1 \end{aligned}\]

where $x$ are the subproblem variables, $z$ is a setup variable that always takes the value one in a solution to the subproblem.

The coefficients of the columns in constraints (1) and (2) of the master are computed using representative variables of the subproblems. You can read this section (TODO Natacha) to understand how we map the subproblem solutions into master columns.

References:

Main loop

This is a description of how the Coluna.ColGen.run! generic function behaves in the default implementation.

The main loop stops when the Coluna.ColGen.stop_colgen method returns true. This is the case when one of the following conditions holds:

  • the master or a pricing subproblem is infeasible
  • the time limit is reached
  • the maximum number of iterations is reached

Otherwise, the main loop runs until there is no more phase or stage to execute.

The method returns:

References:

Coluna.ColGen.new_output — Function
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.

source

Phase loop

This is a description of how the Coluna.ColGen.run_colgen_phase! generic function behaves in the default implementation.

This function is responsible for maintaining the incumbent dual bound and the incumbent master IP primal solution.

The phase loop stops when the Coluna.ColGen.stop_colgen_phase method returns true. This is the case when one of the following conditions holds:

  • the maximum number of iterations is reached
  • the time limit is reached
  • the master is infeasible
  • the master is unbounded
  • a pricing subproblem is infeasible
  • a pricing subproblem is unbounded
  • there is no new column generated at the last iteration
  • there is a new constraint or valid inequality in the master
  • the incumbent dual bound and the primal master LP solution value converged

The method returns:

References:

Coluna.ColGen.before_colgen_iteration — Function

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.

source
Coluna.ColGen.after_colgen_iteration — Function

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.

source

Phase iterator

In the first iterations, the restricted master LP contains a few columns and may be infeasible. To prevent this, we introduced artificial variables $v$ and we activate/deactivate these variables depending on whether we want to prove the infeasibility of the master LP or find the optimal LP solution. The default implementation provides three phases:

Coluna.Algorithm.ColGenPhase0 — Type

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.

source
Coluna.Algorithm.ColGenPhase1 — Type

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.

source
Coluna.Algorithm.ColGenPhase2 — Type

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.

source

Column generation always starts with Phase 0.

The default implementation of the phase iterator belongs to the following type:

Transitions between the phases depend on four conditions:

  • (A) the presence of artificial variables in the master LP solution
  • (B) the generation of new essential constraints (may happen when a new master IP solution is found)
  • (C) the current stage is exact
  • (D) column generation converged

Transitions are the following:

flowchart TB; id1(Phase 0) id2(Phase 1) id3(Phase 2) id4(end) id5(error) id1 --A & !B & C--> id2 id1 --!A & !B & C & D--> id4 id1 -- otherwise --> id1 id2 --!A & !B--> id3 id2 --A & C & D--> id4 id2 -- otherwise --> id2 id3 -- !B & C & D --> id4 id3 -- otherwise --> id3 id3 -- B --> id2 id3 -- A --> id5 style id5 stroke:#f66

References:

Coluna.ColGen.decrease_stage — Function

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

source

Phase output

Coluna.ColGen.new_phase_output — Function
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
source

Stages

A stage is a set of consecutive iterations in which we use a given pricing solver. The aim is to speed up the resolution of the pricing problem by first using an approximate but fast pricing algorithm and then switching to increasingly less heuristic algorithms until the last stage where an exact solver is used. and an exact solver at the last stage. Given a pricing solver, when the column generation does not progress anymore or the pricing solver does not return any new column, the default implementation switch to a more exact pricing solver. Stages are created using the stages_pricing_solver_ids of the ColumnGenerationAlgorithm parameter object. The default implementation implements the interface around the following object:

Coluna.Algorithm.ColGenStageIterator — Type

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.

source

References:

Column generation iteration

This is a description of how the Coluna.ColGen.run_colgen_iteration! generic function behaves in the default implementation.

These are the main steps of a column generation iteration without stabilization. Click on the step to go to the relevant section.

flowchart TB; id1(Optimize master LP) id2{{Solution to master LP is integer?}} id3(Update incumbent primal solution if better than current one) id4(Compute reduced cost of subproblem variables) id5{{Subproblem iterator}} id6(Optimize pricing subproblem) id7(Push subproblem solution into set) id8(Compute dual bound) id9(Insert columns) id10(Iteration output) id1 --> id2 id2 --yes--> id3 id2 --no--> id4 id3 --> id4 id4 --> id5 id5 --subproblem--> id6 id6 --> id7 id7 --> id5 id5 --end--> id8 id8 --> id9 id9 --> id10 click id1 href "#Optimize-master-LP" "Link to doc" click id2 href "#Check-integrality-of-the-master-LP-solution" "Link to doc" click id3 href "#Update-incumbent-primal-solution" "Link to doc" click id4 href "#Reduced-costs-calculation" "Link to doc" click id5 href "#Pricing-subproblem-iterator" "Link to doc" click id6 href "#Pricing-subproblem-optimization" "Link to doc" click id7 href "#Set-of-generated-columns" "Link to doc" click id8 href "#Dual-bound-calculation" "Link to doc" click id9 href "#Columns-insertion" "Link to doc" click id10 href "#Iteration-output" "Link to doc"

Optimize master LP

At each iteration, the algorithm requires a dual solution to the master LP to compute the reduced cost of subproblem variables.

The default implementation optimizes the master with an LP solver through MathOptInterface. It returns a primal and a dual solution.

In the default implementation, the master LP output is in the following data structure:

Coluna.Algorithm.ColGenMasterResult — Type

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.

source

References:

Coluna.ColGen.optimize_master_lp_problem! — Function
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.

source

You can see the additional methods to implement in the result data structures section.

Go back to the column generation iteration overview.

Check the integrality of the master LP solution

The algorithm checks the integrality of the primal solution to the master LP to improve the global primal bound of the branch-cut-price algorithm.

By default, the integrality check is done using the MathProg.proj_cols_is_integer method. It implements the mapping procedure from the paper "F. Vanderbeck, Branching in branch-and-price: a generic scheme, Math.Prog. (2011)". Basically, it sorts the column used in the master LP primal solution in lexicographic order. It assigns a weight to each column equal to the value of the column in the master LP solution. It then forms columns of weight one by accumulating the columns of the fractional solution. If columns are integral, the solution is integral. This is a heuristic procedure so it can miss some integer solutions.

In the case the pricing subproblems are solved by a callback, and some subproblem integer variables are "hidden" from Coluna (values of these variables are usually stored in CustomData associated with the pricing problem solution), the mapping procedure may not be valid. In this case, the integrality should be checked in the "strict" way, i.e., by explicitly verifying that all columns are integer.

Integrality check procedure is set using parameter strict_integrality_check (false by default) of the ColumnGenerationAlgorithm.

If the solution is integral, the essential cut callback is called to make sure it is feasible.

References:

Go back to the column generation iteration overview.

Update incumbent primal solution

If the solution to master LP is integral and better than the current best one, we need to update the incumbent. This solution is then used by the tree-search algorithm in the bounding mechanism that prunes the nodes.

References:

Go back to the column generation iteration overview.

Reduced costs calculation

Reduced costs calculation is written as a math operation in the run_colgen_iteration! generic function. As a consequence, the dual solution to the master LP and the implementation of the two following methods must return data structures that support math operations.

To speed up this operation, we cache data in the following data structure:

Coluna.Algorithm.ReducedCostsCalculationHelper — Type

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
source

Reduced costs calculation also requires the implementation of the two following methods:

Go back to the column generation iteration overview.

Pricing subproblem iterator

The pricing strategy is basically an iterator used to iterate over the pricing subproblems to optimize at each iteration of the column generation. The context can serve as a memory of the pricing strategy to change the way we iterate over subproblems between each column generation iteration.

The default implementation iterates over all subproblems.

Here are the references for the interface:

Coluna.ColGen.AbstractPricingStrategy — Type

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
source
Coluna.ColGen.pricing_strategy_iterate — Function
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.

source

Go back to the column generation iteration overview.

Pricing subproblem optimization

At each iteration, the algorithm requires primal solutions to the pricing subproblems. The generic function supports multi-column generation so you can return any number of solutions.

The default implementation supports optimization of the pricing subproblems using a MILP solver or a pricing callback. Non-robust valid inequalities are not supported by MILP solvers as they change the structure of the subproblems. When using a pricing callback, you must be aware of how Coluna calculates the reduced cost of a column:

The reduced cost of a column is split into three contributions:

  • the contribution of the subproblem variables that is the primal solution cost given the reduced cost of subproblem variables
  • the contribution of the non-robust constraints (i.e. master constraints that cannot be expressed using subproblem variables except the convexity constraint) that is not supported by MILP solver but that you must take into account in the pricing callback
  • the contribution of the master convexity constraint that is automatically taken into account by Coluna once the primal solution is returned.

Therefore, when you use a pricing callback, you must not discard some columns based only on the primal solution cost because you don't know the contribution of the convexity constraint.

Coluna.Algorithm.GeneratedColumn — Type

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
source
Coluna.Algorithm.ColGenPricingResult — Type

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
source

References:

Coluna.ColGen.optimize_pricing_problem! — Function
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
source

You can see the additional methods to implement in the result data structures section.

Go back to the column generation iteration overview.

Set of generated columns

You can define your data structure to manage the columns generated at a given iteration. Columns are inserted after the optimization of all pricing subproblems to allow the parallelization of the latter.

In the default implementation, we use the following data structure:

Coluna.Algorithm.ColumnsSet — Type

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.
source
Coluna.Algorithm.SubprobPrimalSolsSet — Type

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.

source

In the default implementation, push_in_set! is responsible for checking if the column has improving reduced cost. Only columns with improving reduced cost are inserted in the set. The push_in_set! is also responsible to insert he best primal solution to each pricing problem into the SubprobPrimalSolsSet object.

References:

Coluna.ColGen.set_of_columns — Function

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.

source
Coluna.ColGen.push_in_set! — Function

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.

source

Go back to the column generation iteration overview.

Dual bound calculation

In the default implementation, given a vector $\pi \geq 0$ of dual values to the master constraints (1), the Lagrangian dual function is given by:

\[L(\pi) = \pi a + \sum_{k \in K} \max_{l_k \leq \mathbf{1} \lambda^k \leq u^k} (c^k - \pi A^k)\lambda^k + \max_{ \bar{l} \leq y \leq \bar{u}} (\bar{c} - \pi \bar{A})y\]

Let:

  • element $z_k(\pi) \leq \min_i (c^k_i - \pi A^k_i)$ be a lower bound on the solution value of the pricing problem
  • element $\bar{z}_j(\pi) = \bar{c} - \pi \bar{A}$ be the reduced cost of pure master variable $y_j$

Then, the Lagrangian dual function can be lower bounded by:

\[L(\pi) \geq \pi a + \sum_{k \in K} \max\{ z_k(\pi) \cdot l_k, z_k(\pi) \cdot u_k \} + \sum_{j \in J} \max\{ \bar{z}_j(\pi) \cdot \bar{l}_j, \bar{z}_j(\pi) \cdot \bar{u}_j\}\]

More precisely:

  • the first term is the contribution of the master obtained by removing the contribution of the convexity constraints (computed by ColGen.Algorithm._convexity_contrib), and the pure master variables (but you should see the third term) from the master LP solution value
  • the second term is the contribution of the subproblem variables which is the sum of the best solution value of each pricing subproblem multiplied by the lower and upper multiplicity of the subproblem depending on whether the reduced cost is negative or positive (this is computed by ColGen.Algorithm._subprob_contrib)
  • the third term is the contribution of the pure master variables which is taken into account by master LP value.

Therefore, we can compute the Lagrangian dual bound as follows:

master_lp_obj_val - convexity_contrib + sp_contrib

However, if the smoothing stabilization is active, we compute the dual bound at the sep-point. As a consequence, we can't use the master LP value because it corresponds to the dual solution at the out-point. We therefore need to compute the lagrangian dual bound by strictly applying the above formula.

References:

Coluna.ColGen.compute_dual_bound — Function
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.
source

Go back to the column generation iteration overview.

Columns insertion

The default implementation inserts into the master all the columns stored in the ColumnsSet object.

Reference:

Coluna.ColGen.insert_columns! — Function

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.

source

Go back to the column generation iteration overview.

Iteration output

References:

Coluna.ColGen.new_iteration_output — Function
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
source

Go back to the column generation iteration overview.

Getters for Result data structures

Method nameMasterPricing
is_unboundedXX
is_infeasibleXX
get_primal_solX
get_primal_solsX
get_dual_solX
get_obj_valX
get_primal_boundX
get_dual_boundX

References:

Coluna.ColGen.get_primal_bound — Function

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.

source

Go back to the column generation iteration overview.

Getters for Output data structures

Method nameColGenPhaseIteration
get_nb_new_colsX
get_master_ip_primal_solXXX
get_master_lp_primal_solX
get_master_dual_solX
get_dual_boundXX
get_master_lp_primal_boundX
is_infeasibleX

References:

Go back to the column generation iteration overview.

Stabilization

Coluna provides a default implementation of the smoothing stabilization with a self-adjusted $\alpha$ parameter, $0 \leq \alpha < 1$.

At each iteration of the column generation algorithm, instead of generating columns for the dual solution to the master LP, we generate columns for a perturbed dual solution defined as follows:

\[\pi^{\text{sep}} = \alpha \pi^{\text{in}} + (1-\alpha) \pi^{\text{out}}\]

where $\pi^{\text{in}}$ is the dual solution that gives the best Lagrangian dual bound so far (also called stabilization center) and $\pi^{\text{out}}$ is the dual solution to the master LP at the current iteration. This solution is returned by the default implementation of Coluna.ColGen.get_stab_dual_sol.

Some elements of the column generation change when using stabilization.

  • Columns are generated using the smoothed dual solution $\pi^{\text{sep}}$ but we still need to compute the reduced cost of the columns using the original dual solution $\pi^{\text{out}}$.
  • The dual bound is computed using the smoothed dual solution $\pi^{\text{sep}}$.
  • The pseudo bound is computed using the smoothed dual solution $\pi^{\text{sep}}$.
  • The smoothed dual bound can result in the generation of no improving columns. This is called a misprice. In that case, we need to move away from the stabilization center $\pi^{\text{in}}$ by decreasing $\alpha$.

When using self-adjusted stabilization, the smoothing coefficient $\alpha$ is adjusted to make the smoothed dual solution $\pi^{\text{sep}}$ closer to the best possible dual solution on the line between $\pi^{\text{in}}$ and $\pi^{\text{out}}$ (i.e. where the subgradient of the current primal solution is perpendicular to the latter line). To compute the subgradient, we use the following data structure:

Coluna.Algorithm.SubgradientCalculationHelper — Type

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.

source

References:

Coluna.ColGen.update_stabilization_after_master_optim! — Function
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.

source
Coluna.ColGen.update_stabilization_after_pricing_optim! — Function

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
source
Coluna.ColGen.update_stabilization_after_iter! — Function

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
source