2025.1130

Coluna.jl: A Branch-and-Price-and-Cut Framework in Julia

This archive is distributed in association with the INFORMS Journal on Computing under the MIT License.

The software and data in this repository are a snapshot of the software and data that were used in the research reported in the paper Coluna.jl: A Branch-and-Price-and-Cut Framework in Julia by F. Vanderbeck, G. Marques, R. Sadykov, V. Nesello, N. Javerzat, A. Pessoa, T. Bulhões, C. Bentes, V. L. de Lima, and A. Subramanian. The snapshot is based on this SHA in the development repository.

Important: This code is being developed on an on-going basis at https://github.com/atoptima/Coluna.jl/. Please go there if you would like to get a more recent version or would like support

Cite

To cite the contents of this repository, please cite both the paper and this repo, using their respective DOIs.

https://doi.org/10.1287/ijoc.2025.1130

https://doi.org/10.1287/ijoc.2025.1130.cd

Below is the BibTex for citing this snapshot of the repository.

@misc{ColunaIJOC2026,
  author =        {F. Vanderbeck and G. Marques and R. Sadykov and V. Nesello and N. Javerzat and A. Pessoa and T. Bulhões and C. Bentes and V. L. de Lima and A. Subramanian},
  publisher =     {INFORMS Journal on Computing},
  title =         {Coluna.jl: A Branch-and-Price-and-Cut Framework in Julia},
  year =          {2026},
  doi =           {10.1287/ijoc.2025.1130.cd},
  url =           {https://github.com/INFORMSJoC/2025.1130},
  note =          {Available for download at https://github.com/INFORMSJoC/2025.1130},
}

Description

The goal of this repository is to provide the source code of Coluna.jl, a modular and efficient framework for solving large-scale mixed-integer linear programming (MILP) problems via decomposition techniques. It is built on top of MathOptInterface.jl.

Coluna specializes in:

• Dantzig-Wolfe Decomposition: Automating the generation of columns in a branch-and-price context.
• Benders Decomposition: Solving problems by projecting out variables and adding cuts.
• Extensibility: Providing a flexible API to customize subproblem solvers and cutting plane generation.

The repository follows a modular structure inspired by best practices in scientific software development:

• src/: Core implementation of the Coluna.jl framework
• examples/: Example models demonstrating how to use the framework
• docs/: Documentation and usage guides
• test/: Unit and integration tests

For the most up-to-date version of the code and ongoing development, please visit the official repository at https://github.com/atoptima/Coluna.jl.

Requirements

To use this repository, you need:

• Julia (version 1.6 or higher recommended)
• Required Julia packages (automatically installed via the package manager)

---

Installation

To install Coluna.jl, open a Julia session and run:

using Pkg
Pkg.add("Coluna")
Pkg.add("BlockDecomposition")

Usage

Here is an example with the Generalized Assignment Problem.

Let M be the set of machines, J the set of jobs. A machine m has a resource capacity Q[m]. A job j assigned to a machine m has a cost c[m][j] and consumes w[m][j] resource units of the machine m. The goal is to minimize the sum of job costs while assigning each job to a machine and not exceeding the capacity of each machine.

Let x[m][j] equal to one if job j is assigned to machine m; 0 otherwise.

using JuMP, GLPK
using Coluna, BlockDecomposition


M = 1:3;
J = 1:15;
c = [12.7 22.5 8.9 20.8 13.6 12.4 24.8 19.1 11.5 17.4 24.7 6.8 21.7 14.3 10.5; 19.1 24.8 24.4 23.6 16.1 20.6 15.0 9.5 7.9 11.3 22.6 8.0 21.5 14.7 23.2;  18.6 14.1 22.7 9.9 24.2 24.5 20.8 12.9 17.7 11.9 18.7 10.1 9.1 8.9 7.7; 13.1 16.2 16.8 16.7 9.0 16.9 17.9 12.1 17.5 22.0 19.9 14.6 18.2 19.6 24.2];
w = [61 70 57 82 51 74 98 64 86 80 69 79 60 76 78; 50 57 61 83 81 79 63 99 82 59 83 91 59 99 91;91 81 66 63 59 81 87 90 65 55 57 68 92 91 86; 62 79 73 60 75 66 68 99 69 60 56 100 67 68 54];
Q = [1020 1460 1530];

coluna = optimizer_with_attributes(
    Coluna.Optimizer,
    "params" => Coluna.Params(
        solver = Coluna.Algorithm.TreeSearchAlgorithm() # default branch-cut-and-price
    ),
    "default_optimizer" => GLPK.Optimizer # GLPK for the master & the subproblems
);


model = BlockModel(coluna)
@axis(M_axis, M)
@variable(model, x[m in M_axis, j in J], Bin);
@constraint(model, cov[j in J], sum(x[m, j] for m in M_axis) >= 1);
@constraint(model, knp[m in M_axis], sum(w[m, j] * x[m, j] for j in J) <= Q[m]);
@objective(model, Min, sum(c[m, j] * x[m, j] for m in M_axis, j in J));
@dantzig_wolfe_decomposition(model, decomposition, M_axis)
master = getmaster(decomposition)
subproblems = getsubproblems(decomposition)
specify!.(subproblems, lower_multiplicity = 0, upper_multiplicity = 1)
getsubproblems(decomposition)
optimize!(model)

Results

The associated article does not include computational experiments requiring replication.

Ongoing Development

This code is being developed on an on-going basis at the author's Github site.

Support

For support in using this software, submit an issue.